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

vlambda
2020-06-25

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

换硬币（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 数组中的无效元素。

至此，我们离写出题解代码已经很接近了，但还要处理一个编程上的细节：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 数组中的依赖关系

可以看到，子问题的依赖方向是向右、向下的。那么我们应该从左到右、从上到下遍历 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 数组变成一维的。不过考虑到这个空间优化比较难，大家也都不怎么熟悉背包问题，这里我们省去了空间优化的步骤。后面会有专门的背包问题文章讲解相关的技巧。

总结

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

题目	计算目标	维度
322. Coin Change	最小硬币数量	一维
377. Combination Sum IV	方案数	一维
518. Coin Change 2	方案数	二维

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

往期文章

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

vlambda博客
学习文章列表