518零钱兑换II

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 这题很像 494 目标和 那题，但是这个 是完全背包 494那题是01背包（只拿一次）；
        # 其实就是 一个物品可以 拿多次，看看有多少种方法 把固定容量的背包填满；
        # 注意这里是 组合不是排列，2+2+1 和 2+1+2 和 1+2+2 是一样的。
        # 定义 d[j] 是 j容量下 有 d[j]种方式可以凑成总金额；
        # 这种 有多少种方法 的背包问题，递推公式参考 494那题，都是 d[j] += d[j-weight[i]]
        # 初始化考虑要递增不受影响 除了起始位置 d[0]=1，其余都应该被定义为0；
        # 完全背包中，遍历顺序上，背包的遍历需要正序遍历；
        # 完全背包先遍历 物品会 把物品的顺序先定死，所以会是 “组合” ，以本题为例只会有{1,2}而不会有物品乱序的{2,1}；
        # 完全背包先遍历 背包，物品没有先被定死， 会出现 ”排列“ ，以本题为例{1,2}{2,1}都会出现。
        d = [0 for _ in range(amount+1)]
        d[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                d[j] += d[j-coins[i]]
                # print(i,j,d)          # 动态规划打印 方便检查。
        return d[amount]