image.png
实现
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:\
# 硬币无限 完全背包
# D:dp[i][k] = n 表示使用前i种货币 凑成k时 的最小个数
# T:dp[i][k] = min(dp[i][k-x*nums[i]])+x x<k/nums
# B:dp[0][x*nums[0]] = x
if amount == 0:
return 0
len_coins = len(coins)
dp = [[1e4]*(amount+1) for _ in range(len_coins)]
for x in range(amount//coins[0]+1):
dp[0][x*coins[0]] = x
for i in range(len_coins):
dp[i][0]=0
for i in range(1,len_coins):
for j in range(amount+1):
dp[i][j] = min(dp[i-1][j],dp[i][j-coins[i]]+1) if j-coins[i]>=0 else dp[i-1][j]
return -1 if dp[len_coins-1][amount] ==1e4 else dp[len_coins-1][amount]
优化
完全背包状态只依赖上一次和这一次 可以用滚动数组优化
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:\
# 硬币无限 完全背包
# D:dp[i][k] = n 表示使用前i种货币 凑成k时 的最小个数
# T:dp[i][k] = min(dp[i][k-x*nums[i]])+x x<k/nums
# B:dp[0][x*nums[0]] = x
if amount == 0:
return 0
len_coins = len(coins)
dp = [1e4]*(amount+1)
for x in range(amount//coins[0]+1):
dp[x*coins[0]] = x
for i in range(1,len_coins):
for j in range(amount+1):
dp[j] = min(dp[j],dp[j-coins[i]]+1) if j-coins[i]>=0 else dp[j]
return -1 if dp[amount] ==1e4 else dp[amount]
