完全背包问题 - 零钱兑换II - 《算法》

思路

给定不同面额的硬币和一个总金额
写出函数来计算可以凑成总金额的硬币**组合数**

假设每一种面额的硬币有无限个（完全背包）

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

输入: amount = 10, coins = [10]
输出: 1

注意:
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

思路

与「力扣」「力扣」第 377 题（组合总和 Ⅳ）的区别

这道题，第一眼看过去和「力扣」第 377 题：组合总和 Ⅳ 很像，它们的区别在于结果集是否在乎排列顺序：

「力扣」第 377 题：一个组合的不同排列是一个新的组合。[1, 1, 2]、[1, 2, 2]、[2, 1, 2] 视为为不同的组合。
「力扣」第 518 题：一个组合的不同排列在结果集中只出现一次，这一点是「背包问题」的特征，拿东西的顺序不重要。[2, 2, 1] 是一个组合，[1, 2, 2] 和 [2, 1, 2] 不是新的组合。这道题和「力扣」第 39 题：组合总和 很像，只不过：
- 第 39 题问的是所有的组合**列表，应该使用 回溯算法** 求解；
- 第 518 题问的是组合有多少**种，而不是问所有具体的解。应该使用 动态规划** 求解。

这道题可以套用「完全背包」的模型，不过我们这里和大家推导一下公式，以加深对「完全背包」模型的理解。

复习「完全背包」问题

「完全背包」问题的特点是：**
- 本题特殊的地方在于：从背包里选取的物品 **必须刚好装满需要考虑的容量**，而不是小于等于，注意这点细微的区别
「完全背包」问题是「0-1」背包问题的扩展。它们的区别在于
- 「0-1」背包问题：当前考虑的物品拿或者不拿
- 「完全」背包问题：当前考虑的物品拿或者不拿，如果拿，只要背包能装下，就可以一直拿，直到背包装不下为止

求解思路依然是：**一个一个物品考虑，容量一点一点扩大，整个过程是一个 尝试和比较 **的过程。

思考状态和状态转移方程

第 1 步：定义状态

dp[i][j]：硬币列表的前缀子区间 [0, i] 能够凑成总金额为 j 的组合数
1. 说明：背包问题有一个特点，顺序无关，在本题解的最开始，我们强调过这道问题的这个性质，因此可以一个一个硬币去考虑。

第 2 步：状态转移方程

基础状态转移方程，本题解的后半部分有优化
对于遍历到的每一种面值的硬币，逐个考虑添加到「总金额」中。由于硬币的个数可以无限选取，因此对于一种新的面值的硬币 coins[i]，依次考虑选取 0 枚、1 枚、2 枚，以此类推，直到选取这种面值的硬币的总金额超过需要的总金额 j 为止。

状态转移方程是：

dp[i][j] = dp[i - 1][j - 0 * coins[i]] + 
           dp[i - 1][j - 1 * coins[i]] +
           dp[i - 1][j - 2 * coins[i]] + 
           ... + 
           dp[i - 1][j - k * coins[i]]

说明：状态转移方程基于「分类计数原理」：
1. 完成一件事，有 N 类办法
2. 在第 1 类办法中有 m种不同的方法
3. 在第 2 类办法中有 m种不同的方法
4. …….
5. 在第 n 类办法中有 m种不同的方法
6. 那么完成这件事共有：N = m**+m**+ … + m**种不同的方法。
上述公式需要满足：j - k * coins[i] >= 0。dp[i][j] 相对于 dp[i - 1][j] 而言，多考虑的一枚硬币，是当前正在考虑的那枚硬币的面值，coins[i]，而这枚硬币选取的个数（从 0 开始）就是 dp[i][j] 这个问题可以分解的各个子问题的分类标准。

第 3 步：思考初始化

**dp[0][0]** 的值设置为 1，这一点可能比较难理解，但它作为被参考的值，可以使得后续的状态转移方程正确。
1. 原因是：当 dp[i - 1][j - k * coins[i]] 的第 2 维j - k * coins[i] == 0成立的时候，k 个硬币 coin[i] 恰好成为了一种组合。
2. 因此，dp[0][0] = 1 是合理的（代入状态转移方程，值正确）
填写第 1 行（下标为 0 的那一行），也是初始化的时候需要考虑的内容。
1. 第 1 行只考虑第 1 枚硬币 coins[0]，能够组合出的容量只有 coins[0] 的整数倍数。

第 4 步：思考输出

输出就是表格的最后一格的数值，即 dp[len - 1][amount]

第 5 步：考虑空间优化

当前状态行的值，只和上一行的状态值相关，可以使用滚动数组技巧。一个更经典的「空间优化」的方法是采用和「0-1」背包问题相对的赋值的方式，我们留在本题解的后半部分和大家介绍。



const change = function(amount, coins) {
    const len = coins.length;
    if (len == 0) {
      if (amount == 0) {
        return 1;
      }
      return 0;
    }

    const dp = new Array(len).fill(0).map(() => new Array(amount + 1));
    // 题解中有说明应该如何理解这个初始化
    dp[0][0] = 1;

    // 填第 1 行
    for (let i = coins[0]; i <= amount; i += coins[0]) {
      dp[0][i] = 1;
    }

    for (let i = 1; i < len; i++) {
      for (let j = 0; j <= amount; j++) {
        for (let k = 0; j - k * coins[i] >= 0; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
        }
      }
    }
    return dp[len - 1][amount];
}

优化状态转移方程

根据状态转移方程其实可以得到递推公式。状态转移方程的表达形式「看起来」像是一个「无穷级数」，可以通过如下方式得到如下递推公式：
这里 j - k * coins[i] >= 0。将 j 用 coins[i] 替换，得：
这里 j - coins[i] - k * coins[i] >= 0。整理得：
这里 j - k * coins[i] >= 0
1. 将等式（1）- 等式（3），得（4）：dp[i][j] -dp[i][j - coin[i]] = dp[i - 1][j]
2. 整理得（5）：dp[i][j]=``dp[i−``1][j]+``dp[i][j−``coins[i]] ```javascript var change = function (amount, coins) { const len = coins.length;
if (len == 0) { if (amount == 0) { return 1; } return 0; }

const dp = new Array(amount + 1).fill(0); dp[0] = 1; for(let i = coins[0]; i <= amount; i+= coins[0]){ dp[i] = 1; // 只要是coins[0]的倍数, 就至少有一种方法（全部用coins[0]填满） }

for (let j = 0; j < len; j++) { for (let i = coins[j]; i <= amount; i++) { dp[i] = dp[i] + dp[i - coins[j]]; } } return dp[len]; };

```

零钱兑换II

思路

与「力扣」「力扣」 第 377 题（组合总和 Ⅳ）的区别