【leetcode题解——动态规划之完全背包】518.零钱兑换II（python版本详解+表格+dp五部曲）

518. 零钱兑换 II

重点：

本题求组合数，而非排列数。

例如示例：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合，都是 2 2 1，而(2,2,1)(2,1,2)为两种排列

组合不强调元素之间的顺序，而排列强调。

dp五部曲：

1. dp[j]：满足总金额为j的硬币组合数

2. 公式：dp[j]+=dp[j-coins[i]]

dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

3. 初始化：dp[0]初始化为1,其余初始化为0

从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。

下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

4. 遍历顺序：外层i表示不同面额的硬币，内层j表示总金额，都是正序

外层for循环遍历物品，内层for循环遍历背包容量：求得组合数

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

外层for循环遍历背包容量，内层for循环遍历物品：求得排列数

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

5. 举例推导

amount = 5, coins = [1, 2, 5]

	j=0	j=1	j=2	j=3	j=4	j=5
i=0	1	1	1	1	1	1
i=1	1	1	2	2	3	3
i=2	1	1	2	2	3	4

得到dp[5]=4

代码：

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        lenc=len(coins)
        dp=[0]*(amount+1)
        dp[0]=1
        for i in range(lenc):
            for j in range(coins[i],amount+1):
                dp[j]+=dp[j-coins[i]]
        return dp[amount]