经典动态规划：「换硬币」系列三道问题详解

痛定思痛。 2023-02-21 06:15 105阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

转自面向大象编程

换硬币（Coin Change）问题是一道经典的动态规划入门题，但是你可能不太知道，LeetCode 上的换硬币问题其实是一个系列，共三道题目：

*  LeetCode 322. Coin Change（Medium）
 *  LeetCode 377. Combination Sum IV（Medium）
 *  LeetCode 518. Coin Change 2（Medium）

其中，377 题虽然不叫 Coin Change，但是本质上和换硬币问题是一样的。

这一系列是比较考验技巧的三道题目，难度层层递进。第一道题是大家都熟悉的动态规划入门题；第二道题变为求方案数，需要我们不重复不遗漏；第三道题更有难度，需要扩充为二维动态规划，才能准确求出方案数量。

没有做过这个系列三道题的同学，不妨跟着本文看看三道题目的解法，理解其中的思路和技巧。下面我们一道一道地进行分析。

## (一) 第 322 题：求最小硬币数 ##

LeetCode 322. Coin Change（Medium）

> 给定不同面额的硬币 `coins` 和金额 `amount`，计算凑成总金额所需的**最少的硬币个数**。如果没有任何一种方案能组成该金额，返回 -1。每种硬币的数量是无限的。
> 
> 示例：
> 
>     输入: coins = [1, 2, 5], amount = 11
>     输出: 3 
>     解释: 11 = 5 + 5 + 1

这第一道题目大家应该都做过，网上的各种解析也很泛滥。这里我们还是套用[动态规划的解题四步骤][Link 1]来求解。

**第一步，定义子问题。**

我们设硬币面值的集合为。子问题可以定义为：「凑出金额的最小硬币数」。那么原问题就是求。

**第二步，写出子问题的递推关系。**

求「凑出金额的最小硬币数」，我们可以尝试不同的硬币。如果使用了金额为的硬币，问题就变成了「凑出金额的最小硬币数」。我们要从各种尝试中选择硬币数量最小的那个结果。

这样我们就可以写出子问题的递推关系：

当然，不要忘记子问题的 base case：

它的含义是，当 `amount` 为 0 时，不需要任何硬币就已经凑出了目标金额。

**第三步，确定 DP 数组的计算顺序。**

确定 DP 数组计算顺序的重点是看子问题的依赖关系。我们以为例，即有 1 元、2 元、5 元的硬币。这样依赖于、、，全部在的左边。也就是说，DP 数组中的每个元素只依赖其左边的元素。

![format_png 2][] DP 数组中的依赖关系

既然 DP 数组中的依赖关系都是向右指的，那么 DP 数组的计算顺序就是从左到右。

**处理 DP 数组中的无效元素。**

至此，我们离写出题解代码已经很接近了，但还要处理一个编程上的细节：DP 数组中的无效元素。

可能存在一些金额是硬币凑不出来的。例如只有 2 元、5 元的硬币时，就凑不出 1 元、3 元的金额。这样、就是无效元素，不能参与子问题的计算。

为了计算方便，我们可以把无效的子问题用（正无穷大）表示。这是因为子问题的递推关系求的是最小值，正无穷大的值显然不会成为最小值。这样无效元素也能参与计算了。

在编程表示中，我们发现 DP 数组中的值最大也只能是 `amount`（只有 1 元硬币的情况，硬币数量等于金额数），我们可以用 `amount + 1` 表示。DP 数组中的值只要大于 `amount`，就认为是无效元素。

这样，我们就可以写出最终的题解代码：

public int coinChange(int[] coins, int amount) {
        // 子问题：
        // f(k) = 凑出金额 k 的最小硬币数
        
        // f(k) = min{ 1 + f(k - c) }
        // f(0) = 0
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1); // DP 数组初始化为正无穷大
        dp[0] = 0;
        for (int k = 1; k <= amount; k++) {
            for (int c : coins) {
                if (k >= c) {
                    dp[k] = Math.min(dp[k], 1 + dp[k-c]);
                }
            }
        }
        // 如果 dp[amount] > amount，认为是无效元素。
        if (dp[amount] > amount) {
            return -1;
        } else {
            return dp[amount];
        }
    }

这道题进行空间优化很麻烦，所以我们忽略第四步空间优化的步骤。

## (二) 第 377 题：求方案数 ##

LeetCode 377 - Combination Sum IV（Medium）

> 给定一个由正整数组成且不存在重复数字的数组 `nums`，找出和为给定目标正整数 `target` 的组合的个数。**顺序不同的序列视作不同的组合**。
> 
> 示例：`nums = [1, 2, 3]`，`target = 4`。所有可能的组合为：
> 
>     (1, 1, 1, 1)
>     (1, 1, 2)
>     (1, 2, 1)
>     (1, 3)
>     (2, 1, 1)
>     (2, 2)
>     (3, 1)

别看这道题表面上看起来跟换硬币没啥关系，但如果你把数字 `nums` 变成硬币 `coins`，把 `target` 变成 `amount`，它就成了一道如假包换的换硬币问题：

> 给定不同面额的硬币 `coins` 和金额 `amount`，计算凑出该金额的方案的个数。顺序不同的序列视作不同的方案。

这道题和上一题的不同在于，不是求「最小的硬币数量」，而是求「方案的个数」。这样问题的难度又上了一个台阶。

求「方案数」的难度在于要做到不重复、不遗漏。如果是求「最小值」，其实子问题之间可以有重复，也能求出正确的最小值；但是求「方案数」时，子问题之间的重复会导致方案数不正确。这一点一定要特别注意。

**第一步，定义子问题。**

我们还是设硬币面值的集合为。子问题可以定义为：「凑出金额的方案的个数」。那么原问题就是求。

**第二步，写出子问题的递推关系。**

我们可以把凑硬币的方案看成硬币的排列。对于即「凑出金额的方案数」，我们考虑第一个硬币选哪个。以为例，第一个硬币放 1、2 或 5 显然都是不同的方案。如果第一个硬币放的是 1，剩下的金额的方案个数是。这样我们可以得出：

把这个公式推广到一般的硬币面值集合，就得到了子问题的递推关系：

同样的，不要忘记子问题的 base case：

它的含义是「凑出金额 0 的方案数为 1」。这是求「方案数」时一个常见的技巧。所有的最后都要转化为求出来。

**第三步，确定 DP 数组的计算顺序。**

这道题的 DP 数组及其计算顺序和上一题是一样的，这里不再赘述。

![format_png 2][] DP 数组中的依赖关系

DP 数组中不存在什么无效元素。凑不出的金额我们可以用来表示，即方案数为 0。

这样我们就可以写出题解代码了。这一题的主要难度在于递推关系的细节，最终写出的题解代码还是挺简单的：

public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1]; // 默认初始化为 0
        dp[0] = 1; // 注意 base case
        for (int k = 1; k <= target; k++) {
            for (int n : nums) {
                if (k >= n) {
                    dp[k] += dp[k-n];
                }
            }
        }
        return dp[target];
    }

## (三) 第 518 题：不重复的方案数 ##

LeetCode 518. Coin Change 2（Medium）

> 给定不同面额的硬币 `coins` 和金额 `amount`。写出函数来计算可以凑成该金额的硬币组合数。假设每一种面额的硬币有无限个。
> 
> 示例：
> 
>     输入: amount = 5, coins = [1, 2, 5]
>     输出: 4
>     解释: 有四种方式可以凑成总金额:
>     5=5
>     5=2+2+1
>     5=2+1+1+1
>     5=1+1+1+1+1

这道题和上一题的区别在于，顺序不同的序列视为同一种方案。这一个小小的改动，让题目的难度瞬间上升。我们在上一题中写出的子问题递推关系不再适用了。

例如要凑出金额 5，本题中将「2+2+1」和「1+2+2」视为同一种方案。我们不能再像上一题中那样，先考虑第一个硬币是 1、2、5，再看后面的方案了。

那么，如何去除像「2+2+1」和「1+2+2」这样重复了的序列呢？其实，这非常像「排列」跟「组合」的关系：上一题中将顺序不同的序列视为不同的方案，类似「排列」问题；这一题中将顺序不同的序列视为相同的方案，类似「组合」问题。

我们已经在前面的文章中讨论过排列问题与组合问题的关系：

[LeetCode 例题精讲 | 08 排列组合问题：回溯法的候选集合][LeetCode _ _ 08]

要将顺序不同的排列视为同一个组合，只需要考虑所有**有序的排列**，丢弃其他的排列。

对于硬币问题，就是限制硬币选择的次序，先选面额大的硬币，再选面额小的硬币。也就是说，我们只允许「2+2+1」这样**先大后小**的硬币序列出现，不允许「1+2+2」这样的硬币序列。

如何限制硬币选择的次序呢？答案是动态规划增加一个维度，用参数表示当前可选的硬币。

**第一步，定义子问题。**

设硬币面值的集合为。子问题表示用前个硬币（即）凑出金额的方案数。

在一开始，，即可以选择全部的个硬币。假如在当前一步选择了面额第二大的硬币，那么接下来变为，限制后面只能选比小的硬币。

**第二步，写出子问题的递推关系。**

子问题的递推关系是这样的：

这个递推关系是怎么来的呢？考虑子问题，用硬币凑出金额时，我们有两种选择：

第一种选择：拿一个面额最大的硬币，因为一种硬币可以重复拿多次，后面还都可以随便选，方案数为。

第二种选择：决定不再拿面额最大的硬币，后面只能选，方案数为。

你可以会问，为什么没有？其实我们的公式已经把这种情况包括在里面了。

这样，原问题就是，即用全部的个硬币凑出金额 `amount` 的方案数。

另外别忘了子问题的 base case。这道题的 base case 同样比较复杂：

*  当时，。即「凑出金额 0 的方案数为 1」，与上一题一样的技巧。
 *  当时，。硬币用完后，凑不出任何金额。

**第三步，确定 DP 数组的计算顺序。**

我们发现，这一题增加了一个维度，变成了二维动态规划问题。这样我们就更需要确定 DP 数组的计算顺序了。接下来为了讨论方便，我们设硬币的种类为，要凑出的金额（`amount`）为。

首先，DP 数组的有效范围是。在 DP 数组中，base case 位于 DP 数组的最左侧一列和最上方一行，而原问题则位于 DP 数组的右下角，如下图所示。

![format_png 3][] DP 数组的特殊值

这张图中特意把 DP 数组画成一个很扁的长方形，是因为一般情况要比大很多。表示要凑出的金额 `amount`，而表示硬币的种类。

子问题的依赖关系在 DP 数组中是这样子的：

![format_png 4][] DP 数组中的依赖关系

可以看到，子问题的依赖方向是向右、向下的。那么我们应该从左到右、从上到下遍历 DP 数组，计算其中的元素。

最终，我们可以写出这样的题解代码：

public int change(int amount, int[] coins) {
        int m = coins.length;
        int[][] dp = new int[m+1][amount+1];
    
        for (int i = 0; i <= m; i++) {
            for (int k = 0; k <= amount; k++) {
                if (k == 0) {
                    dp[i][k] = 1; // base case
                } else if (i == 0) {
                    dp[i][k] = 0; // base case
                } else {
                    dp[i][k] = dp[i-1][k];
                    if (k >= coins[i-1]) {
                        dp[i][k] += dp[i][k-coins[i-1]];
                    }
                }
            }
        }
        return dp[m][amount];
    }

眼尖的同学可能已经看出来，这其实是一道**背包问题**。那么，这道题可以用背包问题的通用空间优化方法进行优化，把二维的 DP 数组变成一维的。不过考虑到这个空间优化比较难，大家也都不怎么熟悉背包问题，这里我们省去了空间优化的步骤。后面会有专门的背包问题文章讲解相关的技巧。

## 总结 ##

比较换硬币系列三道问题，我们发现它们各有不同，总体难度循序渐进，其实非常适合作为一个系列的练习题。

<table> 
 <thead> 
  <tr> 
   <th>题目</th> 
   <th>计算目标</th> 
   <th>维度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>322. Coin Change</td> 
   <td>最小硬币数量</td> 
   <td>一维</td> 
  </tr> 
  <tr> 
   <td>377. Combination Sum IV</td> 
   <td>方案数</td> 
   <td>一维</td> 
  </tr> 
  <tr> 
   <td>518. Coin Change 2</td> 
   <td>方案数</td> 
   <td>二维</td> 
  </tr> 
 </tbody> 
</table>

如果三道题中有几道你还没有做过，强烈建议你在看完本文后按照这个顺序依次做一遍题目，可以加深对这一系列题目的理解。

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 2]• [Leetcode 惊现马化腾每天刷题 ？ 为啥大佬都这么努力！][Leetcode _ _]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]• [新手使用 GitHub 必备的两个神器][GitHub]• [卧槽！红警代码竟然开源了！！！][Link 4]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 5][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vdzZwcnpadVBJRU5iMG01aWF3dXRJZjkwTjJVYjNkY1B1UDJLWEhKdmFSMUZ2MkZuaWNUdU95M0tjSHVJRUpiZDlsVXlPaWJlWHFXOHRFaG9KR0w5OHFPdy82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVF6Z1Rwa3I5OG9LZjhqcXVpYUx5SnRqcVdrZ1BLaWJVY2dvclVseTFvSk8xS2hRaEowcEhCbHlUenYxWHY2Z2UySmpvblNCTjRodGVYUS82NDA?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/105828328
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9US0FENGF4RmNpYmlielNIOGJqUEhQTFFEWTdOY0w4QjZHOWRJRlVJcmt3bllLaWFPeW9mMWpwNWRadGZpY3pRbWpadHVBV2NKU3o1dXBuTUtvV29pY1EwNDBRLzY0MA?x-oss-process=image/format,png
[LeetCode _ _ 08]: https://blog.csdn.net/kexuanxiu1163/article/details/106345682
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9US0FENGF4RmNpYmlielNIOGJqUEhQTFFEWTdOY0w4QjZHNlU4TW5mMXJyNkRZa25pY3NEbFBiTjhrNWtoU2pHclNGM3lraFRpYmtlRFVZWWFaUElYWU9LdFEvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9US0FENGF4RmNpYmlielNIOGJqUEhQTFFEWTdOY0w4QjZHNFJ1dWxSOWczclpuSlBLSFpkT1R3aWNnVFdiY2JvTVQ1SVQ3bEMwTEVSamhjMHFhazlZVERHUS82NDA?x-oss-process=image/format,png
[LeetCode]: https://blog.csdn.net/kexuanxiu1163/article/details/106846242
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/106774199
[Leetcode _ _]: https://blog.csdn.net/kexuanxiu1163/article/details/106754530
[MySQL _ B_]: https://blog.csdn.net/kexuanxiu1163/article/details/106754537
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/106740545
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/106700185
[Link 4]: https://blog.csdn.net/kexuanxiu1163/article/details/106610365
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJodm5leUhtTURJTW1sOWtJYlVMUGlhUG5pYThpYW5ic1o3Q2trYlFGQTJLU3V3SzA2R3NuT3JMQ2tleHdwYUVoWU1aNHdac1BpY01Uc1ZBLzY0MA?x-oss-process=image/format,png