vlambda博客
学习文章列表

换硬币（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

这第一道题目大家应该都做过，网上的各种解析也很泛滥。这里我们还是套用来求解。

第一步，定义子问题。

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

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

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

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

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

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

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

确定 DP 数组计算顺序的重点是看子问题的依赖关系。我们以 为例，即有 1 元、2 元、5 元的硬币。这样 依赖于 、 、 ，全部在 的左边。也就是说，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 数组及其计算顺序和上一题是一样的，这里不再赘述。

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」这样重复了的序列呢？其实，这非常像「排列」跟「组合」的关系：上一题中将顺序不同的序列视为不同的方案，类似「排列」问题；这一题中将顺序不同的序列视为相同的方案，类似「组合」问题。

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

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

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

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

第一步，定义子问题。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

子问题的依赖关系在 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 数组变成一维的。不过考虑到这个空间优化比较难，大家也都不怎么熟悉背包问题，这里我们省去了空间优化的步骤。后面会有专门的背包问题文章讲解相关的技巧。

总结

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

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

往期文章

原创不易，点个「在看」吧 ↘︎