动态规划——记忆化与表格法详解

动态规划是一种通过保存较小子问题的答案并在之后重复利用它们来解决问题的方法。当同样的子问题会反复出现，而且最终答案可以由这些较小答案构建出来时，它就特别有用。

动态规划主要有两种常见形式：记忆化和表格法。记忆化是在递归求解过程中保存答案。表格法则按自底向上的顺序填写答案，通常借助数组或表格完成。

动态规划在什么时候有效

当两个条件同时满足时，动态规划通常很有用。

第一，子问题会重叠。也就是说，同一个中间结果会被多次需要。第二，较大的答案能够以一致的方式由较小的答案构建出来。

如果不满足这些条件，保存旧结果可能只会增加内存开销，却带来不了太多帮助。

记忆化与表格法

记忆化：自顶向下存储

记忆化从递归思路出发。当算法第一次解决某个子问题时，它会把结果存起来。之后再次遇到同一个子问题时，就直接复用已保存的值，而不是重新计算。

当递推关系很清楚，但所有需要状态的计算顺序并不明确时，这种方式通常更容易使用。

表格法：自底向上构建

表格法从边界条件开始，按一种能保证依赖项在需要时已经可用的顺序来填写各个状态。

当你已经知道一个清晰的迭代顺序，并希望显式控制整张表时，这种方式通常更方便。

动态规划示例：斐波那契数列

斐波那契数列定义为

$$F(0) = 0, \quad F(1) = 1$$

并且当 $n \ge 2$ 时，

$$F(n) = F(n-1) + F(n-2)$$

普通的递归解法会产生重复计算。比如，计算 $F(5)$ 需要 $F(4)$ 和 $F(3)$，而计算 $F(4)$ 时又会再次需要 $F(3)$。这种重复计算正是动态规划要消除的浪费。

斐波那契中的记忆化

使用记忆化时，递推关系保持不变，但每个值在第一次算出后都会被保存。

对于 $F(5)$，有用的计算顺序是：

• 计算并保存 $F(0)=0$
• 计算并保存 $F(1)=1$
• 计算并保存 $F(2)=1$
• 计算并保存 $F(3)=2$
• 计算并保存 $F(4)=3$
• 计算并保存 $F(5)=5$

关键点在于，每个状态只会被计算一次。之后再次需要时，直接读取已保存的值即可。

斐波那契中的表格法

使用表格法时，你从边界条件开始向上构建：

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

这种写法让依赖顺序非常直观：每个新值都只使用已经已知的项。

为什么动态规划可能更快

如果一个问题中真正重要的不同状态只有 $k$ 个，那么动态规划会尽量让这 $k$ 个状态各自只求解一次。这样就能把一棵庞大的递归树，变成规模小得多的计算过程。

具体能快多少取决于问题本身。动态规划并不会自动带来高效率。只有当原始解法中确实存在大量重复计算时，它才会真正发挥作用。

动态规划中的常见错误

在子问题不重叠时使用它

并不是每个递归问题都适合动态规划。如果几乎每个子问题都不同，那么缓存结果可能节省不了多少计算，意义也就不大。

状态定义错误

状态必须包含下一步所需的全部信息。如果遗漏了重要信息，递推关系看起来也许没问题，但最终会得到错误答案。

边界条件写错

边界条件是整个方法的起点。如果初始值错了，后面所有基于它们构建出来的状态都会出错。

按错误顺序填表

表格法只有在每个状态都晚于其依赖状态被填写时才有效。即使递推关系本身正确，填表顺序错了也会失败。

以为动态规划一定是在做最优化

很多经典例子确实是在求最大值或最小值，但动态规划也常用于计数问题和判定问题。真正的信号是子问题可以复用，而不是“最优”这个词本身。

动态规划的应用场景

动态规划常见于编辑距离、最长公共子序列、路径计数、背包类优化，以及某些最短路径问题中。

当你在判断是否该尝试动态规划时，可以先问两个问题：

• 较小的子问题会重复出现吗？
• 较大的答案能由这些较小答案构建出来吗？

如果这两个问题的答案都是肯定的，那么动态规划就是一个很强的候选方法。

试试一个类似的问题

你可以自己尝试这样一个版本：如果每次可以走 $1$ 级或 $2$ 级台阶，那么爬上 $n$ 级台阶一共有多少种方法。它的递推关系很简单，重复子问题也很容易看出来，是学完斐波那契之后很适合继续练习的例子。