记忆化搜索

1. 基本概念

  • 核心定义：记忆化搜索是一种自顶向下的算法优化技术。它在递归的基础上，增加了一个“备忘录”（通常是哈希表或数组），用来记录已经计算过的子问题的结果。
  • 核心思想：“拒绝重复劳动”。
    • 当你第一次遇到某个子问题时，正常计算，并把结果记在小本本上。
    • 当你再次遇到相同的子问题时，直接查小本本，不再重复计算。
  • 本质：它是动态规划的一种实现形式（另一种是自底向上的迭代法）。它保留了递归的代码逻辑，但拥有了动态规划的时间效率。

2. 费曼理解

用最简单的语言解释给“小白”听：

想象你在做一本超厚的数学练习册（递归问题），题目之间有依赖关系。

  • 普通递归（傻算）：
    你做到第 10 题，发现需要第 5 题的答案，于是翻回去算第 5 题。
    做完第 10 题，你做第 12 题，发现又需要第 5 题的答案。于是你又翻回去，重新算了一遍第 5 题！
    这就叫“重复计算”，效率极低。

  • 记忆化搜索（聪明人）：
    你在桌子旁放了一个草稿本（Memo）。
    当你第一次算出第 5 题的答案是 100 时，你把它记在草稿本上：“第 5 题 = 100”。
    当你做第 12 题又需要第 5 题时，你不用重新算，直接看一眼草稿本，抄下 100 继续做。
    这就叫“记忆化”。

3. 内部实现：核心结构

记忆化搜索的代码结构非常固定，通常包含以下三个部分：

组成部分 代码特征 作用
1. 备忘录 memo = {} 或 @lru_cache 用来存储 (参数) -> 结果 的映射关系。
2. 查表 if state in memo: return memo[state] 递归函数开头：先检查这个问题以前有没有算过。如果有，直接返回。
3. 记录 memo[state] = result 返回结果前：把这次算出来的结果存进去，供下次使用。

4. 代码实战：斐波那契数列

对比普通递归，看看记忆化搜索是如何“加速”的。

普通递归（慢）：

1
2
3
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2) # 算 fib(5) 时，fib(3) 被算了两次

记忆化搜索（快）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def fib(self, n: int) -> int:
        # 1. 初始化备忘录
        memo = {}
        
        def helper(n):
            # 2. 查表：如果算过，直接返回
            if n in memo:
                return memo[n]
            
            # 3. 基准情况
            if n <= 1:
                return n
            
            # 4. 计算并记录
            result = helper(n-1) + helper(n-2)
            memo[n] = result # 存入备忘录
            return result
            
        return helper(n)

Python 的“作弊”写法（装饰器）：
你刚才发的 @lru_cache(None) 就是 Python 自动帮你写上面的 memo 逻辑。

1
2
3
4
5
6
7
8
9
from functools import lru_cache

class Solution:
    def fib(self, n: int) -> int:
        @lru_cache(None) # 自动添加记忆功能
        def helper(n):
            if n <= 1: return n
            return helper(n-1) + helper(n-2)
        return helper(n)

5. 复杂度分析

指标 普通递归 记忆化搜索
时间复杂度 指数级 O(2N)O(2^N) 线性 O(N)O(N)
说明 每个节点都分裂成两个，计算量爆炸。 每个子问题（状态）只计算一次，后续都是 O(1)O(1) 查询。
空间复杂度 O(H)O(H) (递归栈) O(N)O(N) (递归栈 + 备忘录空间)

6. 应用场景

什么时候该用记忆化搜索？

  • 一看就是递归结构：题目逻辑用递归写非常自然（如树的遍历、回溯、博弈游戏）。
  • 发现重复计算：在递归树中，发现很多节点的状态是重复的（比如斐波那契、爬楼梯、目标和问题）。
  • 不想写迭代 DP：有时候状态转移方程很难写成 for 循环（比如状态维度很多，或者依赖关系复杂），用记忆化搜索可以**“偷懒”**，直接照着逻辑写递归，加上缓存就能过。

总结：三者的关系

在你的笔记中，可以用这个公式来串联之前的知识点：

动态规划 = 递归 + 记忆化搜索

  • 递归：是骨架，定义了问题的拆解方式（自顶向下）。
  • 记忆化搜索：是优化手段，解决了递归的重复计算问题。
  • 动态规划：是最终形态，既可以是“带缓存的递归”，也可以是“自底向上的循环”。

💡 核心感悟：
记忆化搜索是最符合人类直觉的动态规划写法。当你面对一个复杂的 DP 问题，如果不知道怎么从底向上推导，不妨先试着写一个递归，然后加上 @lru_cache，往往就能直接解决问题！

7.相关

1
2
3
4
TABLE without id file.link AS "题目名称", 数据结构,date
FROM #LeetCode 
WHERE contains(数据结构, "记忆化搜索")
SORT file.mtime DESC