算法

动态规划总结

最近fucking-algorithm 这个算法教学库特别火。其中介绍了很多算法的“套路”，对算法初学者来说非常适用。以下是我读完 动态规划解题核心框架 一节后的归纳总结。

首先，动态规划问题的一般形式就是求最值

这个总结非常有用。如果工作或者面试中碰巧遇到最值问题，又没有解答头绪的时候，可以尝试着用动态规划的思路去分析一下。我想所谓的算法“套路”，无非就是看到 A 就自然会去联系到 B 的路数吧。

求解动态规划的核心问题是穷举

因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

解决穷举的效率问题

动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。(用「备忘录」或者「dp table」来优化递归树，这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已，无非就是用空间换时间的思路)

状态转移方程

啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。

你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法

以上是 labuladong 原文中举例斐波那契数列时写的。我个人的理解，所谓状态转义方程：就是将原问题分解成多个相同类型的子问题，然后写出 base case 问题的解，由 base 层层推导出原问题的过程，并将这个过程用数学方程来表示。 而这里最难的就是如何将原问题分解成多个相同类型的子问题

写出状态转移方程是最困难的。 具体的思路是 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

这里分步说明下：

  1. 明确 base case 这个很简单，基本上等于说是某个状态 = 0 或 1 的时候，问题的解是多少
  2. 明确状态。所谓状态，就是一个会变化的量(也可能是多个)。这里有个“套路”，一般这个变量就是第一步中取值等于 0 或 1 的那个量。
  3. 确定选择。选择会导致第二步里的状态变化。每个选择相当于一个 for 循环，也就是穷举你的选择，然后从所有的选择中选取最值
  4. 明确 dp 函数/数组的定义。一般来说函数的参数就是第二步状态转移中会的变量值，函数的返回值就是题目要求我们计算的量。

框架伪代码：

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

自顶向下 vs 自底向上

从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。大部分递归算法就是这种类型的。

反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

总结

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

阅读每个题目和解法时，多往「状态」和「选择」上靠，才能对这套框架产生自己的理解，运用自如。

参考

动态规划解题核心框架