python换零钱_322.零钱兑换-python

动态规划问题，稍后更新思路

class Solution(object):

def coinChange(self, coins, amount):

"""

:type coins: List[int]

:type amount: int

:rtype: int

"""

INF = float('inf')

dp = []

N = len(coins)

for _ in range(N):

tmp = [INF] * (amount+1)

tmp[0] = 0

dp.append(tmp)

for j in range(1, amount+1):

if j >= coins[0] and dp[0][j-coins[0]] != INF:

dp[0][j] = dp[0][j-coins[0]] + 1

for i in range(1, N):

for j in range(1, amount+1):

if j >= coins[i]:

dp[i][j] = min(dp[i - 1][j], dp[i][j-coins[i]] + 1)

else:

dp[i][j] = dp[i - 1][j]

return dp[len(coins)- 1][amount] if dp[N-1][amount] != INF else -1

进行空间压缩：

class Solution(object):

def coinChange(self, coins, amount):

"""

:type coins: List[int]

:type amount: int

:rtype: int

"""

INF = float('inf')

dp = [0] + [INF]*amount

N = len(coins)

for i in range(amount+1):

for j in range(N):

if i >= coins[j]:

dp[i] = min(dp[i], dp[i-coins[j]]+1)

return dp[amount] if dp[amount] <= amount else -1