引言

其实在一定的条件下贪心算法就可以解决问题，比如凑钱到指定面额的问题。以最熟悉的人民币作为背景，如何用（1，5，10，20，50，100）五种面额的钱币凑出指定数额的钱同时钱数量要尽可能的少，这是我们只需要贪心算法就能解决问题。但是如果有一个很奇怪的国家的发行货币是1，5，11，并且你需要找出面值15的组合，这样贪心算法给出的答案是11+1+1+1+1而我们很轻易的就能发现只要5+5+5就能解决问题。这是因为贪心算法只考虑了眼前最优的情况，并没有给出全局最优解。

递归的问题及改进思路

在这个问题中不难发现，可以问题分解。如最后需要15那么如果最后一枚拿的是11就需要凑4，如果最后一枚拿的是5就需要凑10，如果最后一枚拿的是1就需要凑14，文字表述可能有点绕，公式如下（f（x）表示凑x需要多少枚钱币）

1
f(x) = min{f(x-1),f(x-5),f(x-11)} + 1

从这个公式中其实已经能看到递归的影子，再接下来分析一步将会非常清晰，如求f(x-1)可以参照公式写出下一步的计算公式

1
f(x-1) = min{f(x-1-1),f(x-1-5),f(x-1-11)} + 1

以此类推即可

所以我们其实是可以使用递归解决这个问题的，下面给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int solve(int num){
    if (num == 0){
        return 0;
    }
    int min = Integer.MAX_VALUE;
    if (num >= 1)
        min = Math.min(solve(num - 1) + 1, min);
    if (num >= 5)
        min = Math.min(solve(num - 5) + 1, min);
    if (num >=11)
        min = Math.min(solve(num - 11) + 1, min);
    return min;
}

这个递归代码理论上是没有问题的，计算15可以得到正确的答案，但是当输入的数字比较大时耗时长是小事，会大量占用内存是不能接受的。因为递归算法是指数级增长的，所以我们还是需要提出一个新的思路来解决这个问题。

在这张递推图中我们已经可以看出递推的问题出现在哪里了，下面省略了非常多的计算步骤，但是我们可以看到仅仅在第三层就已经出现了重复计算，计算机不会使用已经计算的结果而是会重新计算一边，导致递推的耗时非常长。

这里我们可以使用备忘录的方式进行解决，也就是通过创建一个map来记录各个值的计算结果来避免进行重复计算。带有备忘录的递归方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution{
	private HashMap<Integer, Integer> cache = new HashMap<>();

    public int makeChange(int amount) {
        if (amount <= 0) return 0;

        // 校验是否已经在备忘录中存在结果,如果存在返回即可
        if (cache.get(amount) != null) return cache.get(amount);

        int min = Integer.MAX_VALUE;
        if (amount >= 1) {
            min = Math.min(makeChange(amount - 1) + 1, min);
        }

        if (amount >= 5) {
            min = Math.min(makeChange(amount - 5) + 1, min);
        }

        if (amount >= 11) {
            min = Math.min(makeChange(amount - 11) + 1, min);
        }

        cache.put(amount, min);
        return min;

    }
}

其实带有备忘录的递归算法的时间复杂度已经相当低了，在这个问题中已经达到了O(n)。所以为什么我们仍然要使用动态规划算法来解决这个问题呢？

最主要的原因就是内存爆炸(StackOverFlowError)。

反正我的电脑是撑不住f(27000)的备忘录递归，有兴趣的可以自己试试自己电脑的极限在哪里:eyes:

很容易看出我们在递归算法中是使用了自顶向下的一种计算思路，所以形成了一棵树，为了节省内存空间我们需要一种自底向上的计算方法来解决这个问题。这种思路的核心思想就是使用迭代来取代递归。

动态转移方程

备忘录表

我们将之前的备忘录中的数据化成一张表格

上图中的f[n]代表凑够n最少需要多少钱币的函数，方块内的数字代表函数的结果

我们通过观察上图中的表格，结合之前给出的公式得到f[1] = min(f[0], f[-5], f[-11]) + 1

对于f[-n]的情况我们视为无穷大，就可以通过f[0]得到f[1]=1

再看看f[5]: f[1] = min(f[4], f[0], f[-6]) + 1,这实际是在求f[4] = 4、f[0] = 0、f[-6]=Infinity中最小的值即0，最后加上1，即1，那么f[5] = 1。

所以其实任何一个节点都是可以通过之前的节点结果计算出来的，而公式又恰好是我们之前给出的递推公式，在这里被称作是动态转移方程

1
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1

这里引出了DP的另一个优势，就是更加节省空间，如我们需要求f(70)那么我们只需要知道 f(59) f(69) f(65) 的值就可以了，其他值是可以直接丢弃的，而备忘录不行。其实当这个动态转移方程出现时我们的题目基本上已经做完了。

但是需要注意的是动态规划问题解题中非常重要的一点就是要确定边界问题，还是硬币找零问题，我们可以确定如果x是负数那么直接视为无穷大，而f(0)应该被赋值为0。

硬币找零问题完整解答

题目会给出所有硬币的面额coins数组和一个总金额数amount，我们首先列出完整的动态转移方程

1
2
f[0] = 0 (n=0)
f[n] = min(f(n-coins[i]) + 1 (n>0)

根据这个动态转移方程我们不难得出正确的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 初始化备忘录,用amount+1填满备忘录,amount+1 表示该值不可以用硬币凑出来
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount+1);
        // 设置初始条件为 0
        dp[0]=0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                // 根据动态转移方程求出最小值
                if(coin <= i) {
                    dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        // 如果 `dp[amount] === amount+1`说明没有最优解返回-1,否则返回最优解
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}

代码中需要注意的是初始化备忘录的时候不能使用可能会误导计算过程的数值如-1这种，只能使用不可能成为最终答案的数值进行初始化。

参考

本文的写作过程中大量参考了作者寻找海蓝96，他的文章链接：https://juejin.cn/post/6844904113889624077