动态规划解题套路框架

509. 斐波那契数

322. 零钱兑换

相信大部分人都对「动态规划」很恐惧，me too！！

每次学完动规都信誓旦旦感觉自己学好了，但是一遇到题目就不知所措，感觉自己学了个寂寞！！！

今天 (2022-04-22 16:59:44) 正式开始动态规划的整理总结，始终坚持认为，「一味的输入」远比「学会输出」效果差得多，所以我希望我自己可以坚持「不断的输出」。好了，进入今天的主要内容！

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等

既然是要求最值，那么核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有「可行解」穷举出来，然后在其中找到「最优解」

但是，如果只是无脑穷举，那么肯定效率极其低下！因为动态规划问题具有一些特殊的特点，可以让我们的穷举变得「聪明」一点

首先，我们来介绍动态规划的三个特点：

• 存在「重叠子问题」：当处理规模为 $n$$n$ 的问题时，中间可能需要处理多个相同且规模为 $n-i$$n-i$ 的问题
• 具备「最优子结构」：问题 $n=\{n_1,n_2,n_3\}$$n = \{n_1,n_2,n_3\}$，问题 $n$$n$ 的最优解当且仅当问题 $n_1,n_2,n_3$$n_1, n_2, n_3$ 为最优解时取得；换句话说，我们可以通过求子问题 $n_1,n_2,n_3$$n_1, n_2, n_3$ 的最优解，来得到问题 $n$$n$ 的最优解
• 正确的「状态转移方程」

由于存在「重叠子问题」，所以我们可以通过「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算

这里先给出本人研究出来的一个思维框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

按照上面的思维框架，可以套用下面的伪代码：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

下面通过「斐波那契数列问题」和「凑零钱问题」来详解动态规划的基本原理。前者主要是让你明白什么是「重叠子问题」（斐波那契数列没有求最值，所以严格来说不是动态规划问题），后者主要举集中于如何「列出状态转移方程」

斐波那契数列

题目详情可见 斐波那契数

这个题目相信大家肯定都见过，算是道入门题。之所以放在这里详细分析，是为了可以更好的理解「重叠子问题」的概念

相信大家肯定都是有思路的，下面先使用迭代的思路去解决问题。不出意外是可以顺利通过所有测试用例且未超时！

public int fib(int n) {
    if (n == 0 || n == 1) return n;
    int[] dp = new int[n  + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

现在我们尝试用递归的思路去解决该问题 (没有思路的小伙伴可以先去刷二叉树的题目，锻炼自己的递归思维)

public int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

显然，也是顺利通过了所有的测试用例！但使用递归比迭代耗时长了很多，这是为什么呢？

我们先画出上述递归的递归树看看 (假定 n = 20)

可以看到其实我们的递归中存在很多的冗余计算，如图中标注出来的两个分支f(18)和f(17)。这也正是本文开头所说的「重叠子结构：当处理规模为 $n$$n$ 的问题时，中间可能需要处理多个相同且规模为 $n-i$$n-i$ 的问题」

所以我们可以通过「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算

具体思路：记录子结构的结果，当递归某一子结构时，判断该子结构是否已被计算过。如果已经被计算过，直接从记录中读取结果；否则才去执行该子结构

具体优化代码如下：

private int[] emeo = new int[n + 1];
public int fib(int n) {
    if (n == 0 || n == 1) return n;
    // 备忘录中存在该子结构
    if (emeo[n] != 0) return emeo[n];
    // 备忘录中存在该子结构，记录该子结构的结果
    emeo[n] = fib(n - 1) + fib(n - 2);
    return emeo[n];
}

瞬间就快了很多，因为我们几乎把所有的冗余都去除了

至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和常见的动态规划解法已经差不多了，只不过这种解法是「自顶向下」进行「递归」求解，我们更常见的动态规划代码是「自底向上」进行「递推」求解。而「自底向上」进行「递推」求解其实就是前文使用迭代的方法求解 -> 传送门

这里详细解释一下「自顶向下」和「自底向上」

• 自顶向下：从一个规模较大的原问题比如说f(20)，向下逐渐分解规模，直到f(1)和f(2)这两个 base case，然后逐层返回答案
• 自底向上：从最底下、最简单、问题规模最小、已知结果的f(1)和f(2) (base case) 开始往上推，直到推到我们想要的答案f(20)

注意：一般在递归中，记录子结构结果的数据结构叫「备忘录：emeo」；而在递推中，记录子结构结果的数据结构叫「DP table」

根据迭代求解的思路，很容易给出这个问题的「状态转移方程」：

何为「状态转移方程」，其实就是明确给出「当前状态」是如何从「之前状态」转移过来的方程

回到题目中，即f(n)是从f(n-1)和f(n-2)转移 (相加) 过来的

最后的最后，给出一个空间上优化的思路：由于f(n)只和f(n-1) && f(n-2)相关，故可以只用两个变量来存储这两个状态，然后不断更新

public int fib(int n) {
    if (n == 0 || n == 1) return n;
    int f0 = 0, f1 = 1;
    int f = 0;
    for (int i = 2; i <= n; i++) {
        f = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    return f;
}

凑零钱问题

题目详情可见 零钱兑换

这个问题主要是为了让大家更好的理解「最优子结构」的概念

抛出一个生活中的问题：三门课「语文，数学，英语」，求你考出的最高总成绩？

答案很简单，当然就是语文考最高，数学考最高，英语考最高，最后的总成绩必然最高，为💯！！现在是不是有点理解「最优子结构」是什么东东了！！！

我们的原问题是「最高总成绩」，原问题具有三个子结构「语文成绩，数学成绩，英语成绩」，这三个子结构互相独立，互不影响，所以上述问题符合「最优子结构」

但是，如果加一个条件：语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏

现在回到凑零钱的问题上

分析：原问题「用最少的硬币数凑出总金额为 11」，如果知道凑出 10 的最少硬币数，那么只需要在该数量上 +1 即可得到原问题的答案 (在 10 的基础上增加一枚 1 元硬币即可)！因为硬币的数量是没有限制的，所以子问题之间没有相互制约，是互相独立的

现在根据开头给出的思维框架深度分析：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

• 明确 base case：显然是当amount = 0时，返回为 0
• 明确「状态」：原问题和子问题中会发生变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额amount
• 明确「选择」：导致「状态」产生变化的行为。目标金额为什么变化呢？因为在选择硬币，每选择一枚硬币，目标金额就会相应的减少。所以说「所有的硬币面值集合」就是「选择」(每次都可在集合中选择任意一枚硬币)
• 明确 dp 数组/函数的定义：这里采用自顶向下的解法，所以会有一个递归的dp函数，一般来说函数的参数就是状态转移中会变化的量，即：「状态」；函数的返回值就是题目要求我们计算的量

就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义dp函数dp(n)表示，输入一个目标金额n，返回凑出目标金额n所需的最少硬币数量

根据上面的分析，我们可以很容易的写出完整代码：

public int coinChange(int[] coins, int amount) {
    return dp(coins, amount);
}
// 定义：输入目标金额 amount，返回所需最少硬币数
// 状态：目标金额 amout
// 选择：所有可选硬币集合 coins
private int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 做选择
    int res = Integer.MIN_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解
        if (subProblem == -1) continue;
        // 在子问题中选择最优解
        res = Math.min(res, subProblem + 1);
    }
    return res == Integer.MIN_VALUE ? -1 : res;
}

根据上面的代码，很容易给出这个问题的「状态转移方程」：

至此，这个问题其实就解决了，但是此时还存在「重叠子问题」。比如当amount = 11, coins = {1, 2, 5}时，画出其递归树，如下图所示：

递归算法的时间复杂度分析：子问题总数 $\times$$\times$ 解决每个子问题所需的时间

子问题总数为递归树的节点个数，但算法会进行剪枝，剪枝的时机和题目给定的具体硬币面额有关，所以可以想象，这棵树生长的并不规则，确切算出树上有多少节点是比较困难的。对于这种情况，我们一般的做法是按照最坏的情况估算一个时间复杂度的上界

假设目标金额为n，给定的硬币个数为k，那么递归树最坏情况下高度为n (全用面额为 1 的硬币)，然后再假设这是一棵满k叉树，则节点的总数在 $O(k^n)$$O(k^n)$ 这个数量级

接下来看每个子问题的复杂度，由于每次递归包含一个for循环，复杂度为 $O(k)$$O(k)$，相乘得到总时间复杂度为 $O(k^n)$$O(k^n)$，指数级别

优化一：带备忘录的递归

private int[] emeo;
public int coinChange(int[] coins, int amount) {
    emeo = new int[amount + 1];
    Arrays.fill(emeo, -666);
    return dp(coins, amount);
}
private int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (emeo[amount] != -666) return emeo[amount];
    // 做选择
    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解
        if (subProblem == -1) continue;
        // 在子问题中选择最优解
        res = Math.min(res, subProblem + 1);
    }
    emeo[amount] = res == Integer.MAX_VALUE ? -1 : res;
    return emeo[amount];
}

在这里给出一版超时版本的答案

原因：当结果为 -1 时，emeo[amount]没有更新

private int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (emeo[amount] != Integer.MAX_VALUE) return emeo[amount];
    // 做选择
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解
        if (subProblem == -1) continue;
        // 在子问题中选择最优解
        emeo[amount] = Math.min(emeo[amount], subProblem + 1);
    }
    return emeo[amount] == Integer.MAX_VALUE ? -1 : emeo[amount];
}

更改：

xxxxxxxxxx
// 其余逻辑不变！！
emeo[amount] = emeo[amount] == Integer.MAX_VALUE ? -1 : emeo[amount];
return emeo[amount];

优化二：带 DP 的递推

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

xxxxxxxxxx
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    // base case
    dp[0] = 0;
    for (int i = 1; i < dp.length; i++) {
        for (int coin : coins) {
            // 非法目标金额
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

注意：为什么不直接初始化为 int 型的最大值Integer.MAX_VALUE呢？因为后面有dp[i - coin] + 1，这就会导致整型溢出