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]