记忆化

递归树中许多分支会反复询问同一个子问题；记忆化把已经求出的输入—输出对缓存起来，将递归树折叠成状态 DAG，使同一状态再次出现时直接复用、每个节点只真正求值一次。它保留自顶向下、按需展开的控制流，只计算从初始问题可达的状态；代价是递归开销、哈希或数组查表和缓存空间。正确性依赖函数在同一状态上结果稳定，若状态遗漏了影响结果的环境，缓存会复用错误答案。

令 $F(0)=0,F(1)=1$，$F(k)=F(k-1)+F(k-2)$。求 $F(4)$ 时，先递归求 $F(3)$，它再求 $F(2)$；基例给出 $F(2)=1$，写入缓存。返回上层得到 $F(3)=2$ 后，$F(4)$ 的另一个依赖 $F(2)$ 已经存在，可以直接读出，于是 $F(4)=3$。图中重复出现的调用分支因此合并成同一状态，而不是同一计算仍执行多次。

求 $F(n)$ 只会访问 $0,\dots ,n$。每个状态最多做一次加法，因而是 $O(n)$ 次算术运算、$O(n)$ 个缓存项和最坏 $O(n)$ 栈深。这里把加法视作单位成本；若要求任意大整数的精确值，还要计算随 $n$ 增长的位数成本。缓存消除了重复求值，并没有缩短最初向下递归的链。

状态键必须包含所有影响答案的信息。区间问题只缓存左端点而遗漏右端点，会把不同区间合并；网格路径只用 $(i,j)$ 作键，要求障碍布局在这次求解期间固定。布局改变后应失效缓存或把布局版本纳入键。随机性、副作用和外部环境同样不能在没有语义说明时被缓存隐藏。

无环本身还不足以保证终止：状态 $x$ 若总要先求 $x+1$，依赖链没有环，却永远到不了基例。有限可达图排除了这种情况。

有环依赖需要另行处理。例如 $A$ 要先算 $B$，$B$ 又要先算 $A$，两个结果都尚未写入缓存，普通记忆化仍会无限递归。访问中标记可以发现环，却不能自动算出环上的答案；若问题具有固定点语义，还需专门的迭代或图算法。

缓存淘汰对纯函数可以保持结果正确，却会让被删状态再次计算，因此不能继续无条件宣称“每个状态只计算一次”。在状态很多或结果很大时，应同时比较缓存空间与重算成本。

解析中的PEG有序选择理路解析表达式文法 PEGParsing expression grammar · PEG以有序选择、序列和不消费前看定义确定前缀识别结果的文法。先规定唯一识别结果，Packrat理路Packrat 记忆化解析Packrat parsing缓存固定PEG每个规则在每个输入位置的结果，避免回溯时重复求值。再以“规则、输入位置”为键，同时缓存成功与失败。固定良构文法、结果不依赖外部可变状态且每格工作有界时，才能由线性表项数推出线性时间；需要保留CFG多种语法树时，不能把所有结果硬压成一个成功终点。记忆化也用于图搜索、游戏求值和最优化递推，关键仍是正确界定子问题及其全部结果。

它是 动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。 的自顶向下实现，函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。 的输入构成状态键。与表格法相比，记忆化适合稀疏可达状态和复杂转移；解析、博弈搜索、递归下降与 DAG理路有向无环图Directed acyclic graph · DAG不含有向环的有向图。 计算都可通过缓存把重叠子问题降为一次求值。

在上述有限无环模型中，缓存不淘汰时，记忆化保证每个实际到达状态计算一次；若状态空间本身为全部子集，便得到子集 DP理路子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。的指数上界，而非自动多项式。树宽 DP理路树宽上的动态规划treewidth dynamic programming · DP on tree decompositions以最大独立集的完整逐袋计算，证明树分解边界状态、合并去重与回溯，并区分宽度、袋数和分解成本。在树分解 bag 上缓存边界赋值，复杂度指数集中在宽度。自顶向下是否访问更少状态取决于实例可达性，最坏仍需与完整状态 DAG 比较，不能把“有缓存”当复杂度证明。