把解过的答案再用一遍

又解一遍同样的

递归把大问题
劈成小问题来解。
斐波那契正是这样。
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 才大一点点，
纯递归的柱子
就像要冲出屏幕一样窜上去。
记忆化的柱子
几乎纹丝不动。
不把同一个答案再解一遍，
就这一点，
分开了慢与快。

小结

动态规划
名字唬人，
里头却就三步。
察觉自己在又解一遍同样的，
把解过的答案记下来，
再用就快得多。
把下面的卡片一个个点开，
小结这三步。

又解一遍 → 记下来 → 快得多。(回收分治不重叠、故无需便条这点)

上回的分治里，
劈出来的块互不重叠，
所以没什么可记的。
那儿正是岔路口。
当块重叠时，
也就是同一个小问题
老是又冒出来时，
记下来这一手
才终于改变了一切。