零钱兑换 | blog

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例2：

1 2	输入：coins = [2], amount = 3 输出：-1

示例3：

1 2	输入：coins = [1], amount = 0 输出：0

示例4：

1 2	输入：coins = [1], amount = 1 输出：1

示例5：

1 2	输入：coins = [1], amount = 2 输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

题解

暴力递归

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。

为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制约，是互相独立的。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

java代码如下：

public int coinChange(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 求最小值，所以初始化为正无穷
    int res = Integer.MAX_VALUE;
    for (var p : coins) {
        int tmp = coinChange(coins, amount - p);
        //子问题无解，跳过
        if(tmp == -1) continue;
        res = Math.min(res, 1 + tmp);
    }
    // 问题无解时返回 -1
    return res == Integer.MAX_VALUE ? -1 : res;
}

至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，因为画出递归树就会发现好多问题是被重复计算了的。

当然，该程序直接交上去会超时。

递归算法的时间复杂度分析：子问题总数 x 每个子问题的时间。

子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。

带备忘录的递归

只需要稍加修改，就可以通过备忘录消除子问题：

HashMap<Integer, Integer> memo = new HashMap<>();

public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查找备忘录,避免重复计算
    if(memo.containsKey(amount)){
        return memo.get(amount);
    }
    int res = Integer.MAX_VALUE;
    for (var p : coins) {
        int tmp = coinChange(coins, amount - p);
        //子问题无解，跳过
        if(tmp == -1) continue;
        res = Math.min(res, 1 + tmp);
    }
    if(res == Integer.MAX_VALUE)
        res = -1;
    // 记入备忘录
    memo.put(amount,res);
    return res;
}

显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

这个代码交上去是OK的

dp 数组的迭代解法

当然，我们也可以自底向上使用 dp table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

根据我们文章开头给出的动态规划代码框架可以写出如下解法：

public int coinChange(int[] coins, int amount) {
    // 数组的大小为 amount + 1，初始值也为 amount + 1
    // 因为凑成 amount 金额的硬币数最多只有 amount 个，所以可以初始化为 amount+1
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    // base case
    dp[0] = 0;
    //外层循环在遍历所有状态的取值
    for (int i = 1; i < amount + 1; i++) {
        //内层循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

总结

本文展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。

参考

动态规划详解