零钱兑换 2 是另一种典型背包问题的变体。

看过了动态规划和背包问题的套路，这篇继续按照背包问题的套路，列举一个背包问题的变形。
本文聊的是 LeetCode 第 518 题 Coin Change 2，题目如下：

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

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

示例 2:

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

示例 3:

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

注意:

你可以假设：

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数
    1. int change(int amount, int[] coins);
    PS：至于 Coin Change 1，在我们前文 动态规划套路详解 写过。

    我们可以把这个问题转化为背包问题的描述形式：
    有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，    每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
    这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「    完全背包问题**」，没啥高大上的，无非就是状态转移方程有一点变化而已。
    下面就以背包问题的描述形式，继续按照流程来分析。

    解题思路

    第一步要明确两点，「状态」和「选择」。
    这部分都是背包问题的老套路了，我还是啰嗦一下吧：
    状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
    明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：
  1. for 状态1 in 状态1的所有取值：
  2.     for 状态2 in 状态2的所有取值：
  3.         for ...
  4.             dp[状态1][状态2][...] = 计算(选择1，选择2...)

第二步要明确dp数组的定义。
首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组。
dp[i][j]的定义如下：
若只使用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包。
换句话说，翻译回我们题目的意思就是：
若只使用coins中的前i个硬币的面值，若想凑出金额j，有dp[i][j]种凑法。
经过以上的定义，可以得到：
base case 为dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
我们最终想得到的答案就是dp[N][amount]，其中N为coins数组的大小。
大致的伪码思路如下：

  1. int dp[N+1][amount+1]
  2. dp[0][..] = 0
  3. dp[..][0] = 1
  4. for i in [1..N]:
  5.     for j in [1..amount]:
  6.         把物品 i 装进背包,
  7.         不把物品 i 装进背包
  8. return dp[N][amount]

第三步，根据「选择」，思考状态转移的逻辑。
注意，我们这个问题的特殊点在于物品的数量是无限的，所以这里和之前写的背包问题文章有所不同。
如果你不把这第i个物品装入背包，也就是说你不使用coins[i]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果。
如果你把这第i个物品装入了背包，也就是说你使用coins[i]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。
首先由于i是从 1 开始的，所以coins的索引是i-1时表示第i个硬币的面值。
dp[i][j-coins[i-1]]也不难理解，如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额j - coins[i-1]。
比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。
综上就是两种选择，而我们想求的dp[i][j]是「共有多少种凑法」，所以dp[i][j]的值应该是以上两种选择的结果之和：

  1. for (int i = 1; i <= n; i++) {
  2.     for (int j = 1; j <= amount; j++) {
  3.         if (j - coins[i-1] >= 0)
  4.             dp[i][j] = dp[i - 1][j] 
  5.                      + dp[i][j-coins[i-1]];
  6. return dp[N][W]

最后一步，把伪码翻译成代码，处理一些边界情况。
用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了一些边界问题：

  1. int change(int amount, int[] coins) {
  2.     int n = coins.length;
  3.     int[][] dp = amount int[n + 1][amount + 1];
  4.     // base case
  5.     for (int i = 0; i <= n; i++) 
  6.         dp[i][0] = 1;
  7.     for (int i = 1; i <= n; i++) {
  8.         for (int j = 1; j <= amount; j++)
  9.             if (j - coins[i-1] >= 0)
  10.                 dp[i][j] = dp[i - 1][j] 
  11.                          + dp[i][j - coins[i-1]];
  12.             else 
  13.                 dp[i][j] = dp[i - 1][j];
  14.     }
  15.     return dp[n][amount];
  16. }

而且，我们通过观察可以发现，dp数组的转移只和dp[i][..]和dp[i-1][..]有关，所以可以压缩状态，进一步降低算法的空间复杂度：

  1. int change(int amount, int[] coins) {
  2.     int n = coins.length;
  3.     int[] dp = new int[amount + 1];
  4.     dp[0] = 1; // base case
  5.     for (int i = 0; i < n; i++)
  6.         for (int j = 1; j <= amount; j++)
  7.             if (j - coins[i] >= 0)
  8.                 dp[j] = dp[j] + dp[j-coins[i]];
  9.     return dp[amount];
  10. }

Python

  1. class Solution:
  2.     def change(self, amount: int, coins: List[int]) -> int:
  3.         size = len(coins)
  4.         dp = [0 for i in range(amount+1)]
  5.         dp[0] = 1
  6.         for i in range(size):
  7.             for j in range(1, amount+1):
  8.                 if j-coins[i]>=0:
  9.                     dp[j] = dp[j]+dp[j-coins[i]]
  11.         return dp[amount]

这个解法和之前的思路完全相同，将二维dp数组压缩为一维，时间复杂度 O(N*amount)，空间复杂度 O(amount)。
至此，这道零钱兑换问题也通过背包问题的框架解决了。