自底向上的状态转移
复习
- 从递归到记忆化搜索：自顶向下加缓存
- 动态规划从哪里来：状态与转移
- 递归与栈：递归有调用开销
TL;DR
- 自底向上从最小的状态出发，逐步算出更大的状态
- 它不用递归，而是按依赖顺序填表
- 与记忆化搜索本质相同，只是方向相反
- 关键是确定一个满足依赖的计算顺序
正文
记忆化搜索是“自顶向下”：从大问题出发，缺哪个子问题就算哪个。还有一种方向，反过来从最小的问题开始，一步步往大推——这就是自底向上的动态规划。
从小往大填表
还是斐波那契。与其从 F(n) 往下递归，不如反过来：
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
……
一路推到 F(n)
开一张表，从最小的 F(0)、F(1) 开始，按顺序把每一项填出来。填到 F(n) 时，它依赖的两项早就填好了，直接取来相加即可。
没有递归，没有调用栈，只有一个循环和一张表。
和记忆化是什么关系
两者其实在算同一个东西，区别只在方向：
- 记忆化：自顶向下，用到才算，边递归边缓存
- 自底向上：自底向上，按顺序把每个状态都算一遍
很多时候，把记忆化“翻个方向”，就能改写成自底向上。两者的结果一致，权衡也相近：
- 自底向上：没有递归开销，常数更小，还可能顺着状态关系优化空间（比如斐波那契只需保存前两项，不必存整张表）
- 记忆化：写法更贴近原始递推，只算真正用到的状态，遇到稀疏的依赖时更划算
顺序，是关键
自底向上有一个必须小心的点：计算顺序要满足依赖。
也就是：算出某个状态时，它依赖的所有状态必须已经算好。斐波那契里从小到大正好满足，所以顺理成章。可有些问题里，状态之间的依赖关系不那么直观，随便排个顺序就会“用到还没算的值”。
理清状态之间的依赖、给出一个合法的计算顺序，是自底向上能否成功的前提。 这也再次说明：动态规划的难点，往往在“状态与转移的设计”和“顺序的安排”，而不在代码本身。
思考题 1
自底向上和自顶向下（记忆化）的本质区别是什么？
思考题 2
为什么自底向上特别在意“计算顺序”？
小结
知识点
- 自底向上从最小状态逐步推算更大状态
- 用循环和表代替递归
- 与记忆化本质相同、方向相反
- 必须保证计算顺序满足依赖
参考资料
- Wikipedia(zh)：动态规划：自底向上的实现方式
- Wikipedia(zh)：记忆化：与自底向上相对的实现方式
思考题答案（仅供参考）
思考题 1
本质都是把每个子问题只算一次并保存结果。区别在方向：自顶向下从原问题出发、按需递归计算并缓存；自底向上从最小状态出发、按确定的顺序把所有状态依次算出来。方向不同，结果一致。
思考题 2
因为算某个状态时，它依赖的状态必须先已经算好。若顺序不当，就会在计算时用到尚未求出的值，结果出错。所以必须先理清状态间的依赖，排出一个合法的计算顺序。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪