从递归到记忆化搜索
复习
- 动态规划从哪里来：重叠子问题是关键
- 递归：函数调用自身
- 时间与空间的交换：缓存能省下重复计算
TL;DR
- 记忆化搜索在递归基础上加一层缓存
- 算过的子问题直接查表，不再重复计算
- 它是“自顶向下”的动态规划
- 代码接近原始递归，因此容易理解和修改
正文
动态规划的第一个前提是“重叠子问题”。既然同一个子问题会被反复用到，那就把它只算一次、把答案记下来。这个想法的最直接实现，就是记忆化搜索（memoization）。
给递归加一个记事本
回到斐波那契。原来的递归慢，是因为 F(3) 被算了无数遍。解决办法很简单：准备一张表，每次要算 F(n) 时先查表——
- 表里已经有
F(n)：直接返回，不再计算 - 表里没有：老老实实递归算一遍，再把结果记进表里
加的这点“记事本”，效果却是颠覆性的：每个子问题只会被真正计算一次，之后全是查表。代价从指数级，一下子降到线性级。
它是“自顶向下”的
记忆化搜索的结构是自顶向下的：从原问题出发，需要哪个子问题，就递归去算哪个。
这种方向的好处是贴合直觉。你几乎不需要改变原来的递归思路，只是在入口加一句“先查表”，出口加一句“存表”，就完成了从暴力递归到高效算法的蜕变。它把“用空间换时间”用到了极致，而且改写成本极低。
代价是什么
当然，记忆化也有代价：
- 仍然依靠递归，所以有调用栈的开销，深度太大时可能栈溢出
- 需要额外的存储来缓存结果
- 每个子问题都要走一遍函数调用，常数上比“直接填表”略大
但它胜在写法自然、改动小。当递推关系容易写、而计算顺序不太好理清时，记忆化往往是最省心的选择。
而如果想把递归的调用开销也省掉，就可以换成另一种方向——从最小的子问题出发，一步步往上算。这就是下一章的“自底向上”。
思考题 1
记忆化搜索是如何消除重复计算的？
思考题 2
记忆化搜索相比普通递归，多付出了什么？
小结
知识点
- 记忆化搜索为递归加上结果缓存
- 每个子问题只真正计算一次
- 它是自顶向下的动态规划
- 保留递归开销，但改动小、易理解
参考资料
- Wikipedia(zh)：记忆化：缓存函数结果以避免重复计算
- Wikipedia(zh)：动态规划：自顶向下与自底向上两种形式
思考题答案（仅供参考）
思考题 1
它在递归入口先查缓存：若该子问题的结果已经算过，就直接返回；没算过才真正递归计算，并把结果存入缓存。这样每个子问题只被计算一次，重复计算被彻底消除。
思考题 2
多付出的是额外的存储（用来缓存子问题结果），以及仍然保留的递归调用开销（调用栈、函数调用常数）。换来的是大幅减少的重复计算，整体效率显著提升。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪