闭包记忆化通过私有缓存将递归dp时间复杂度从指数级降至线性，关键在于闭包内自引用、可靠键生成（如${n}|${capacity}）和缓存管控（上限/lru）。
递归函数配合闭包实现记忆化，是突破动态规划性能瓶颈的一种自然、低侵入的解法——它不改变原问题的逻辑结构，却能将指数级重复计算压降到线性时间复杂度。
为什么传统递归在DP问题中会卡住
像01背包、斐波那契、最长公共子序列这类问题，天然适合用递归描述：每一步决策依赖子问题结果。但朴素递归会反复进入相同参数组合，比如 knapsack(3, 8) 可能在调用树中出现数十次。测试表明，25个物品的01背包递归调用可达三千多万次，耗时超60秒。根本原因是：没有缓存中间状态，每次都要重算。
闭包如何安全封装记忆化逻辑
关键不是“加个 cache 对象”，而是让缓存与递归调用链深度绑定。常见错误是只对顶层调用做 memoize，而内部仍调用原始函数。正确做法是：
- 用 IIFE 或高阶函数创建私有作用域，把 cache 和递归函数一起封闭其中
- 确保函数体内所有递归调用都指向**当前闭包内定义的函数本身**（而非全局同名函数）
- 例如：fib = (function() { const cache = {}; return function(n) { ... cache[n] = fib(n-1) + fib(n-2); ... } })() —— 这里 fib 是闭包内自引用，缓存必命中
键生成必须可靠且轻量
缓存失效往往源于键不准。多参数场景下不能简单用 JSON.stringify([a, b])，因为浮点误差、undefined、对象引用、参数顺序都可能破坏一致性。实用建议：
- 整数/字符串参数：直接拼接，如 `${n}|${capacity}`
- 含数组或对象：先做浅克隆+排序+过滤空值，再 stringify
- 避免用 Map 直接存对象作 key，因引用不同即视为不同键
- 对背包类二维状态，用二维数组索引映射为一维键更高效：`i * 1000 + w`（假设容量上限1000）
防止缓存失控的底线措施
记忆化本质是空间换时间，但放任不管会导致内存暴涨甚至 OOM。尤其在树形DP或状态维度高的场景中：
- 给缓存加数量上限，例如 if (cache.size > 10000) cache.clear()
- 优先使用 LRU 策略（如 lru-cache 库），自动淘汰冷数据
- 若函数被长期持有（如挂到全局或事件监听器），需提供 .clear() 方法手动释放
- 开发期加日志：console.log('cache hit:', key, cache.has(key))，确认是否真生效
它不是银弹，但对中等规模、逻辑清晰的DP问题，闭包记忆化比硬写自底向上DP更快落地、更易调试，也更贴近人类思维。真正拖慢性能的，常常不是算法本身，而是缓存没走通，或是键设计错了一位。
