动态规划 怎么工作

同样的东西又算一遍

递归把大问题拆成小问题来解，斐波那契正是这样。
fib(5) 调用 fib(4) 和 fib(3)，fib(4) 又调用 fib(3) 和 fib(2)。仔细一看，fib(2) 在这根枝上、那根枝上反复出现。
在下面的树里点一个节点看看。

同一个小问题在树上到处出现。（点节点 → 相同的值全部高亮）

同一个 fib(2) 不是算一次，而是算了好几次，fib(3) 也一样。
n 一变大，这种重复就会吓人地膨胀。
已经算出的答案还一遍遍重算，谁看了都觉得可惜。

把答案记下来

办法出奇地简单：把算过一次的答案记在便条上。
下次再需要同样的东西，不用重算，直接从便条上拿来用。只算第一次见到的，见过的直接拿来用就行。
点按钮，一个个处理调用。

第一次见到的就算出来记下，见过的就从便条上拿来用。这就是记忆化。

计算只在第一次做一回，其余全从便条上拿，同样的东西算两遍的事就一下子没了。
像这样把算好的答案记下来再用，叫作记忆化。
名字听着唬人，说穿了就是“记下来”。

从下往上填表

同样的想法也可以倒过来用：不从上往下拆，而是从最底下的小值开始，往上填表。
fib(0) 和 fib(1) 本来就知道。两个相加得 fib(2)，fib(1) 和 fib(2) 相加得 fib(3)。
下面的格子已经写好了，上面的格子只要做加法。

从 0,1 开始，一格格往上填。（下一格 = 正下方两格之和 · 自底向上）

这种办法连便条都用不着，因为表本身就是便条。
从下往上按顺序扫一遍，就再也不用重算。
记忆化是“需要时再记”，这个则是“事先全记好”，道理是一样的。

一下子快了

那么能快多少？光是记下来这一招，差别就大得惊人。
单纯递归连重复的也全算，n 越大，活儿就像爆炸一样暴涨；记忆化每格只算一次，活儿只和 n 成正比。
把 n 一点点加大，比一比两者，差距一目了然。

同一个 n 下要算的次数。（单纯递归 = 指数爆炸 · 记忆化 = 与 n 成正比的线性）

n 只要稍微大一点，单纯递归的柱子就像要冲破屏幕一样往上蹿，记忆化的柱子却几乎不动。
同样的答案不再重算，就这一点，分出了慢和快。

总结

动态规划名字听着难，说穿了只有三步。
发现同样的东西在重算，把算过一次的答案记下来，再拿来用，于是一下子快了。
把下面的卡片一张张点开，总结这三步。

同样的东西又算一遍 → 记下来 → 一下子快了。也顺带回顾：分治的块互不重叠，所以用不着记。

前面看过的分治，切开的块互不重叠，所以没什么可记的。
岔路口就在这里。块和块重叠时，也就是同样的小问题一再出现时，“记下来”这一招才会改变一切。