形式陈述

记忆化把递归函数对参数状态 $x$ 的结果存入表 $M[x]$；再次遇到同一状态时直接返回。它要求子问题结果只依赖被选作键的状态信息，且依赖图无导致未定义循环，或另有固定点语义。若共有 $N$ 个可达状态、每个状态计算转移成本至多 $C$，总时间通常为 $O(NC)$，空间为 $O(N)$ 加递归栈。它是自顶向下动态规划，与按拓扑次序填表的自底向上方法等价于同一递推。

直觉

递归树中许多分支会反复询问同一个子问题。记忆化把树折叠成状态 DAG，每个节点只真正求值一次。

例子与边界

朴素 Fibonacci 递归重复计算 $F(k)$，加缓存后只计算 $F(0),\dots ,F(n)$，时间降为 $O(n)$。区间 DP 的键必须包含左右端点；遗漏影响结果的参数会错误合并不同状态。缓存随机或有副作用的函数可能改变语义，除非这些效应也进入键或被隔离。记忆化只访问从初始问题可达的状态，可能优于填满整个表；但哈希和递归开销可能更高。

推论与应用

记忆化广泛用于解析、图搜索、游戏求值和最优化递推，也是把清晰递归定义转化为高效实现的直接技术。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。