记忆化搜索通过缓存已计算的子问题结果，避免重复递归调用，将斐波那契等重叠子问题的时间复杂度从o(2ⁿ)降至o(n)，本质是以空间换时间；常用实现包括手动字典缓存、@lru_cache和python 3.9+的@cache装饰器。
核心思路是让函数“记住”自己算过的结果，下次遇到相同输入直接返回，跳过重复计算。
为什么缓存能大幅降低计算量
递归中存在大量重叠子问题——比如算 fib(10) 时，fib(7) 会被调用多次。原始递归不保存中间结果，每次都要从头展开整棵调用树，时间复杂度达 O(2ⁿ)。缓存把每个 n 对应的结果存下来，后续调用直接查表，总计算次数降到 O(n)，本质是用少量内存换来指数级提速。
三种常用缓存实现方式
- 手动字典缓存（最直观）：在函数内维护一个 dict，调用前先查键是否存在；不存在则计算并存入，再返回
- @lru_cache 装饰器（最推荐）：一行加在函数上，@lru_cache(maxsize=None) 即启用无容量限制缓存；它自动处理参数哈希、命中判断和结果复用
- @cache 装饰器（Python 3.9+）：比 lru_cache 更轻量，等价于 @lru_cache(maxsize=None)，适合不需要淘汰策略的场景
使用时的关键注意点
- 函数必须是纯函数——相同输入永远返回相同输出，不能依赖外部状态或随机值
- 参数需支持哈希（如 int、str、tuple），避免传 list 或 dict 这类不可哈希类型
- 缓存会持续占用内存，若输入范围极大且访问稀疏，可设 maxsize=128 等合理上限，启用 LRU 淘汰
- 调试时可用 func.cache_info() 查看命中率、当前缓存数量等，验证是否生效
不只是斐波那契，这些场景也适用
任何满足“重叠子问题 + 最优子结构”的递归都可受益：
- 爬楼梯、组合总数、背包问题等动态规划类题目
- 解析嵌套 JSON、遍历带环图结构（配合 visited 标记）
- 编译器中的表达式求值、语法树遍历
- 业务中常见的多级分类查询、权限树展开
