动态规划从哪里来

复习

　　贪心有时会错，回溯又太慢。介于两者之间，有一类非常强大的方法叫动态规划（dynamic programming，简称 DP）。理解它的起点，是一个“重复计算”的问题。

　　还记得斐波那契数列吗？F(n) = F(n-1) + F(n-2)。直接写递归：

F(n)：
    如果 n 是 0 或 1，返回 n
    返回 F(n-1) + F(n-2)

　　看着简洁，却慢得吓人。因为算 F(5) 要算 F(4) 和 F(3)；而算 F(4) 时又要算 F(3)——F(3) 被重复计算了很多次，越往下重复越多，代价呈指数增长。

　　这就引出了动态规划的第一个前提：重叠子问题——同一个子问题会被反复遇到。

　　前面讲过分治，它也是把问题拆成子问题。但两者有个关键区别：

　　正因为重叠，动态规划才有发挥空间：既然同一个子问题要算很多遍，那就只算一次，把结果存起来。这一存，指数级的重复计算就消失了。

　　动态规划的第二个前提是最优子结构：整个问题的最优解，可以由子问题的最优解组合出来。

　　比如求最短路，从 A 到 C 的最短路如果经过 B，那么 A 到 B 那段也必然是最短的——否则换一段更短的，整体就更优了。有了这个性质，我们才能放心地“用子问题的最优解拼出全局最优解”。

　　设计动态规划，最难也最关键的一步，是定义状态：用哪些量来描述一个子问题。

　　状态定好了，就能写出状态转移——也就是“大状态如何由小状态推导出来”。这套“状态 + 转移”的框架，就是动态规划的灵魂。选对状态，问题就解了一半；状态选错，怎么推导都别扭。

　　下一章，我们先从最贴近递归的写法入手：记忆化搜索。

思考题 1

　　动态规划和分治的关键区别是什么？

思考题 2

　　什么是“重叠子问题”？为什么它会让普通递归变得很慢？

　　分治的子问题相互独立、互不重叠，各算一次即可；动态规划的子问题相互重叠，同一个子问题会被反复用到。正因重叠，动态规划才需要“只算一次并缓存结果”。

　　重叠子问题指同一个子问题会被多次遇到。比如斐波那契递归里 F(3) 被反复计算。若不缓存，每次都重新算一遍，重复量随层数急剧膨胀，导致代价指数增长。

设计师 | 南国微雪