记忆化搜索是通过缓存已计算的子问题结果来优化递归的方法，适用于存在重叠子问题且函数为纯函数的场景，如斐波那契、背包问题等；实现时需用标准化参数作key查表存表，注意避免缓存爆炸、引用类型key失效及副作用干扰。
记忆化搜索是递归优化的常用手段，核心思想是把已计算过的子问题结果缓存起来，避免重复递归调用。它不改变递归逻辑，只在“查表—计算—存表”环节做干预，用额外空间换取时间效率提升。
什么时候该加记忆化？
当递归函数存在重叠子问题，且函数是纯函数（相同输入总返回相同输出）时，就适合加记忆化。典型场景包括：斐波那契、爬楼梯、背包问题、树形DP中的节点状态计算等。如果每次递归入参都唯一，或结果依赖外部可变状态，则记忆化无效甚至出错。
怎么实现记忆化？
最常用方式是在函数内部维护一个缓存对象或Map：
- 用参数组合（如数字、字符串、JSON序列化后的数组）作为key；多参数可用
[a, b].toString()或JSON.stringify([a, b])生成唯一键（注意对象引用和undefined需预处理） - 每次进入函数先查缓存，命中则直接返回；未命中则递归计算，保存结果后再返回
- 也可用闭包封装缓存，让记忆化逻辑与业务逻辑分离，例如写一个
memoize(fn)高阶函数
要注意的细节
记忆化不是万能银弹，实际使用中容易踩坑：
- 缓存爆炸：参数组合过多（如浮点数精度、长字符串、深层嵌套对象）会导致内存占用失控，需评估输入规模并考虑LRU策略或手动清理
- 引用类型作key不可靠：直接用对象/数组当Map的key，会因引用不同而被当作不同键；必须标准化为字符串或原始值
- 副作用干扰：若递归过程中修改了外部变量或DOM，即使输入相同，结果也可能不同，此时加记忆化会掩盖bug
对比动态规划（DP）
记忆化搜索是DP的自顶向下形式，而传统DP是自底向上填表。两者时间复杂度通常一致，但记忆化更贴近原问题逻辑，易于理解和调试；DP则空间常可优化（如滚动数组），且无递归调用栈开销。对深度过大的递归，还需警惕栈溢出，必要时改用迭代+显式栈模拟。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
