322零钱兑换

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 经典的 完全背包问题，在固定背包容量情况下，求凑满背包 最少的物品数；
        # 设定 d[j] 为 j容量下， 凑满背包 最少物品数为 d[j]；
        # 完全背包还是 要正序遍历 背包，参考 《518零钱兑换II》
        # d[j] = 有i物品和没i物品的最少值 = min( d[j-weight[i]]+1 , d[j] )
        # 注意初始化为了不让 min 导致值被覆盖，所以初始化为 一个很大的值。只有d[0]=0
        d = [2**31-1 for _ in range(amount+1)]
        d[0]=0
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                d[j] = min(d[j],d[j-coins[i]]+1)
                # print(d)
        if d[amount]==2**31-1:       # 递推公式没起作用，找不到对应的最小数量。
            return -1
        return d[amount]