记忆化

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

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

朴素 Fibonacci 递归重复计算 $F(k)$，时间指数；缓存每个 $k$ 后每个状态只求一次，时间 $O(n)$、空间 $O(n)$。网格路径若状态为坐标 $(i,j)$，障碍布局固定时可缓存；若布局会动态改变却未纳入键，旧结果失效。

含环递归可能在结果写入缓存前再次访问同一状态，导致无限递归；需三色标记、固定点迭代或改成图算法。缓存无界增长也可能比重算更昂贵，工程中常配合淘汰策略，但淘汰不应改变纯函数正确性。

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

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

Memoization 只保证每个实际到达状态计算一次；若状态空间本身为全部子集，便得到子集 DP公理库子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。的指数上界，而非自动多项式。树宽 DP公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions在 nice tree decomposition 的小 bag 边界上记录状态，以 f(k)n 时间求解近树图问题。在树分解 bag 上缓存边界赋值，复杂度指数集中在宽度。自顶向下是否访问更少状态取决于实例可达性，最坏仍需与完整状态 DAG 比较，不能把“有缓存”当复杂度证明。