> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/summary/bei-bao-wen-ti/untitled.md).

# Untitled

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

| 牛客网                                                                                                                    | LeetCode                                                           | 力扣                                                              | 难度 |
| ---------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------ | --------------------------------------------------------------- | -- |
| [零钱兑换 II](https://www.nowcoder.com/practice/521cead04d1442899767578c3aa395f0?tpId=295\&fromPut=pc_wzcpa_labuladong_sf) | [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/) | [518. 零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2/) | 🟠 |

**———–**

零钱兑换 2 是另一种典型背包问题的变体，我们前文已经讲了 [经典动态规划：0-1 背包问题](https://labuladong.github.io/algo/3/25/82/) 和 [背包问题变体：相等子集分割](https://labuladong.github.io/algo/3/25/83/)。

**读本文之前，希望你已经看过前两篇文章**，看过了动态规划和背包问题的套路，这篇继续按照背包问题的套路，列举一个背包问题的变形。

本文聊的是力扣第 518 题「 [零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2/)」，我描述一下题目：

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

我们要完成的函数的签名如下：

```java
int change(int amount, int[] coins);
```

比如说输入 `amount = 5, coins = [1,2,5]`，算法应该返回 4，因为有如下 4 种方式可以凑出目标金额：

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

如果输入的 `amount = 5, coins = [3]`，算法应该返回 0，因为用面额为 3 的硬币无法凑出总金额 5。

> PS：至于零钱兑换 I，在我们前文 [动态规划套路详解](https://labuladong.github.io/algo/3/23/68/) 写过。

**我们可以把这个问题转化为背包问题的描述形式**：

有一个背包，最大容量为 `amount`，有一系列物品 `coins`，每个物品的重量为 `coins[i]`，**每个物品的数量无限**。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「**完全背包问题**」，没啥高大上的，无非就是状态转移方程有一点变化而已。

下面就以背包问题的描述形式，继续按照流程来分析。

#### 解题思路 <a href="#jie-ti-si-lu" id="jie-ti-si-lu"></a>

**第一步要明确两点，「状态」和「选择」**。

状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」嘛，背包问题的套路都是这样。

明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：

```python
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            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` 数组的大小。

大致的伪码思路如下：

```python
int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
    for j in [1..amount]:
        把物品 i 装进背包,
        不把物品 i 装进背包
return dp[N][amount]
```

**第三步，根据「选择」，思考状态转移的逻辑**。

注意，我们这个问题的特殊点在于物品的数量是无限的，所以这里和之前写的 [0-1 背包问题](https://labuladong.github.io/algo/3/25/82/) 文章有所不同。

**如果你不把这第 `i` 个物品装入背包**，也就是说你不使用 `coins[i-1]` 这个面值的硬币，那么凑出面额 `j` 的方法数 `dp[i][j]` 应该等于 `dp[i-1][j]`，继承之前的结果。

**如果你把这第 `i` 个物品装入了背包**，也就是说你使用 `coins[i-1]` 这个面值的硬币，那么 `dp[i][j]` 应该等于 `dp[i][j-coins[i-1]]`。

> PS：由于 `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]` 的值应该是以上两种选择的结果之和**：

```java
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= amount; j++) {
        if (j - coins[i-1] >= 0)
            dp[i][j] = dp[i - 1][j] 
                     + dp[i][j-coins[i-1]];
return dp[N][W]
```

> PS：有的读者在这里可能会有疑问，不是说可以重复使用硬币吗？那么如果我确定「使用第 `i` 个面值的硬币」，我怎么确定这个面值的硬币被使用了多少枚？简单的一个 `dp[i][j-coins[i-1]]` 可以包含重复使用第 `i` 个硬币的情况吗？

对于这个问题，建议你再仔回头细阅读一下我们对 `dp` 数组的定义，然后把这个定义代入 `dp[i][j-coins[i-1]]` 看看：

若只使用前 `i` 个物品（可以重复使用），当背包容量为 `j-coins[i-1]` 时，有 `dp[i][j-coins[i-1]]` 种方法可以装满背包。

看到了吗，`dp[i][j-coins[i-1]]` 也是允许你使用第 `i` 个硬币的，所以说已经包含了重复使用硬币的情况，你一百个放心。

**最后一步，把伪码翻译成代码，处理一些边界情况**。

我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了一些边界问题：

```java
int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++) 
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++)
            if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else 
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}
```

而且，我们通过观察可以发现，`dp` 数组的转移只和 `dp[i][..]` 和 `dp[i-1][..]` 有关，所以可以使用前文讲的 [动态规划空间压缩技巧](https://labuladong.github.io/algo/3/23/72/)，进一步降低算法的空间复杂度：

```java
int change(int amount, int[] coins) {
    int n = coins.length;
    int[] dp = new int[amount + 1];
    dp[0] = 1; // base case
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= amount; j++)
            if (j - coins[i] >= 0)
                dp[j] = dp[j] + dp[j-coins[i]];
    
    return dp[amount];
}
```

这个解法和之前的思路完全相同，将二维 `dp` 数组压缩为一维，时间复杂度 O(N\*amount)，空间复杂度 O(amount)。

至此，这道零钱兑换问题也通过背包问题的框架解决了。