第 45 章记忆化搜索——让递归飞起来

🏗️ 前情回顾：第 44 章你学会了回溯——递归地枚举所有可能。但你也发现了一个问题：回溯可能会反复走同一条路。其实不止回溯，就连最朴素的斐波那契递归也在重复计算。本章教你一个精巧的技巧——算过的就记下来，下次直接用。

🎯 本章目标

学完这一章，你能：

识别递归中的"重复计算"，把它量化出来
用记忆化数组"算过就存，存了就用"
掌握记忆化搜索的标准框架
理解自顶向下（记忆化）和自底向上（DP）的关系
用记忆化解决网格路径、数字三角形等经典问题
认识到记忆化搜索是递归到动态规划的桥梁

📖 故事引入

想象你在做数学作业，遇到一道很难的计算题。你绞尽脑汁算了 10 分钟，终于算出了结果是 42。你把答案写在草稿纸上。

半小时后，另一道题又问到了完全相同的计算。你是重新再算 10 分钟，还是翻翻草稿纸，把 42 直接抄过来？

当然是抄过来！这就是记忆化搜索的核心思想：算过一次的东西，记在小本本上，下次遇到直接查，绝不重算。

你回想一下第 26 章斐波那契的递归版：F(5) 调用 F(4) 和 F(3)，F(4) 又调用 F(3) 和 F(2)……F(3) 被算了 2 次，F(2) 被算了 3 次，F(1) 被算了 5 次！n 一大，重复计算就像滚雪球，把程序拖到几乎死机。

如果每次算出一个 F(k) 就记在数组 memo[k] 里，下次再需要 F(k) 时直接查表——斐波那契从指数级直接降到线性！

🧱 知识讲解

45.1 重复计算有多可怕

来看看纯递归 fib(6) 的计算树：

                    fib(6)
                   /      \
              fib(5)      fib(4)
             /    \       /    \
        fib(4)   fib(3) fib(3) fib(2)
        /   \    /   \  /   \
   fib(3) fib(2) ...

你数一数：fib(3) 被算了 3 次，fib(2) 被算了 5 次。n 再大一点，重复次数呈指数增长——fib(40) 就需要超过 3 亿次函数调用！

🔍 类比：就像你每次出门都重新买一遍衣服鞋子——明明柜子里已经有了。纯递归就是这种"健忘症"，算过就忘。

45.2 记忆化数组：算过就存

魔法很简单——加一个数组：

cpp

long long memo[100];  // 记忆化数组，-1 表示"还没算过"

long long fib(int n) {
    if (n <= 2) return 1;          // 边界
    if (memo[n] != -1)             // 查表：算过吗？
        return memo[n];            // 算过了，直接用！
    return memo[n] = fib(n-1) + fib(n-2);  // 没算过，算了存起来
}

int main() {
    memset(memo, -1, sizeof(memo)); // 初始化为 -1（表示未计算）
    cout << fib(50) << endl;        // 瞬间出结果！
    return 0;
}

关键点：memo[n] != -1 含义是"这个值已经算过了"。这里 -1 是"未计算"的标记。为什么选 -1？因为斐波那契数列的值都是正数，-1 永远不会是合法结果。

⚠️ 选择"未计算标记"时，必须选一个永远不可能是合法结果的值。比如计算阶乘时不能选 0（因为 0! = 1，而 memo 初始为 0 就会混淆）。

45.3 记忆化搜索标准框架

把记忆化的模式抽象出来，任何递归问题都可以套：

cpp

// 框架：
返回值 dfs(状态参数...) {
    if (边界条件) return 边界值;
    if (memo[状态] 已被计算) return memo[状态];
    
    返回值 = 由 dfs(更小的状态) 计算得出;
    return memo[状态] = 返回值;   // 存起来再返回
}

三步走：

查表：如果状态已经被计算过，直接返回存储的值
计算：像普通递归一样计算
存储：把结果存入备忘录，再返回

45.4 网格路径问题

问题：一个 m×n 的网格，从左上角走到右下角，每次只能向右或向下走一步。有多少条不同的路径？

纯递归：

cpp

int paths(int x, int y, int m, int n) {
    if (x == m && y == n) return 1;      // 到达终点
    if (x > m || y > n) return 0;        // 越界
    return paths(x+1, y, m, n) + paths(x, y+1, m, n);
}

这个纯递归会大量重复！从 (1,1) 到 (1,2) 再到 (2,2) 和从 (1,1) 到 (2,1) 再到 (2,2)——到达 (2,2) 这个状态被算了两次。

记忆化版：

cpp

long long memo[25][25];
memset(memo, -1, sizeof(memo));  // -1 表示未计算

long long paths(int x, int y, int m, int n) {
    if (x == m && y == n) return 1;
    if (x > m || y > n) return 0;
    if (memo[x][y] != -1) return memo[x][y];   // 查表
    return memo[x][y] = paths(x+1,y,m,n) + paths(x,y+1,m,n);
}

每个格子只被计算一次，时间复杂度从指数降到 O(m×n)。

45.5 数字三角形

问题：数字三角形顶上有 1 个数，往下每一行多一个数。从顶部出发，每次向左下或右下走一格，求到达底部时经过的数字之和的最大值。

例如：

定义状态：dfs(i, j) 表示从第 i 行第 j 列出发，到达底部的最大路径和。

cpp

int a[105][105];      // 数字三角形
int memo[105][105];
int n;

int dfs(int i, int j) {
    if (i == n) return a[i][j];           // 边界：最后一行
    if (memo[i][j] != -1) return memo[i][j];
    return memo[i][j] = a[i][j] + max(dfs(i+1, j), dfs(i+1, j+1));
}

45.6 记忆化 → DP 的桥梁

记忆化搜索是自顶向下的：从大问题出发，一路拆到小问题，边走边记。

动态规划（DP）是自底向上的：先算小问题，用数组存起来，逐步算到大问题。

	记忆化搜索	自底向上 DP
方向	从大到小（递归）	从小往大（循环）
实现	递归 + memo 数组	循环填 dp 表
状态空间	只算"能到达"的状态	遍历所有状态
适用	状态转移不规律、图/树型结构	表格型、递推式清晰的场景
栈溢出	深度大时有风险	没有

同一个数字三角形，自底向上的 DP 写法：

cpp

for (int j = 1; j <= n; j++) dp[n][j] = a[n][j];  // 底部
for (int i = n-1; i >= 1; i--)                     // 往上推
    for (int j = 1; j <= i; j++)
        dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
cout << dp[1][1] << endl;

🧠 记忆化搜索和 DP 本质一样：用空间换时间，避免重复计算。很多 DP 初学者更习惯记忆化——它更贴近"人脑思考问题"的方式。熟悉之后，再学 DP 会水到渠成。

✋ 动手试试

试试 1：分别用纯递归和记忆化递归计算 fib(45)，对比运行时间。用 clock() 计时（需要 #include <ctime>），感受"一个飞起来，一个等半天"的巨大差异。

试试 2：实现数字三角形的记忆化搜索，输入 n 和三角形数据，输出最大路径和。测试数据：n=4，三角形如示例（答案应为 7+3+8+7=25 或 7+8+1+7=23，最大是 7+3+1+7=18？请自己验证）。

试试 3：在网格路径问题中把 m 和 n 逐渐增大，分别测试纯递归和记忆化能承受多大。纯递归可能 m+n=15 就卡住了，记忆化轻松处理到 20×20。

⚠️ 容易犯的错

错 1："未计算"标记选错了

❌ 用 memset(memo, 0, sizeof(memo)) 做阶乘记忆化，然后用 if (memo[n]) 判断——但 0! = 1，1! = 1，都能和"未计算"混淆

✅ 用 -1 或其他合法结果永远不会出现的值

错 2：忘记初始化 memo 数组

❌ int memo[100]; 全局变量自动初始化为 0，但 0 可能恰好是合法答案

✅ 始终显式初始化：memset(memo, -1, sizeof(memo));

错 3：记忆化和递归参数不匹配

❌ memo[n] 存了结果，但递归函数有两个参数，状态是二维的

✅ 记忆化数组的维度必须覆盖所有状态变量：memo[i][j]

错 4：忘记 return 记忆化结果

❌ if (memo[n] != -1) memo[n]; // 查了但没返回

✅ if (memo[n] != -1) return memo[n]; // 查到了就返回

📝 练习

基础题

1. 选择题

（1）不记忆化时，递归计算 fib(5) 共调用了多少次 fib(1)？
A. 1 B. 3 C. 5 D. 8

（2）记忆化搜索的核心思想是？
A. 删掉递归用循环 B. 算过的存起来下次直接用 C. 多开几个线程 D. 把 int 改成 long long

（3）记忆化搜索和自底向上 DP 的共同本质是？
A. 都用递归 B. 都用循环 C. 用空间换时间，避免重复计算 D. 都用全局变量

2. 填空题

（1）记忆化搜索三步走：____ → ____ → ____。

（2）memo 数组初始化时，标记值必须是一个____的值。

（3）自顶向下对应____，自底向上对应____。

提高题

3. 编程题 — 爬楼梯问题

每次可以爬 1 级或 2 级台阶，问爬到第 n 级有多少种不同的方法？（n ≤ 50）

用记忆化搜索实现。注意：这和斐波那契有什么关系？

4. 编程题 — 最小路径和

给定 m×n 网格，每个格子有一个非负整数，从左上角走到右下角（每次右下），求路径上数字之和的最小值。用记忆化搜索。

挑战题

5. 编程题 — 背包问题（记忆化版）

有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。同一件物品只能选一次。问最多能装多少价值？（N ≤ 100, C ≤ 1000）

用记忆化搜索：dfs(i, cap) 表示"考虑前 i 件物品、背包还剩 cap 容量"时的最大价值。

🧠 本章小结

记忆化搜索 = 递归 + 备忘录

核心思想：算过的就存起来，下次直接用
  · memo 数组：memo[状态] = 计算结果
  · 标记未计算：选一个合法结果不会出现的值（如 -1）

框架：
  ① 查表 —— if (memo[状态] 已算) return memo[状态]
  ② 计算 —— 像普通递归一样算
  ③ 存储 —— return memo[状态] = 计算结果

经典应用：
  斐波那契 → 从 O(2^n) 到 O(n)
  网格路径 → 每个子问题只算一次
  数字三角形 → 自顶向下记忆化 vs 自底向上 DP

自顶向下 vs 自底向上：
  记忆化 = 递归，从大问题出发，边走边记
  DP     = 循环，从小问题出发，逐步填表
  本质相同：用空间换时间

📝 配套练习

共7题。从一维memo→二维memo→方案数计数，记忆化的三种memo模式。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1464	https://hydro.ac/p/luogu-P1464	三维memo、记忆化框架
◆ 拓展	luogu-P1028	https://hydro.ac/p/luogu-P1028	记忆化递推、递归→DP
◆ 拓展	luogu-P1044	https://hydro.ac/p/luogu-P1044	记忆化、卡特兰数
◆ 拓展	luogu-P1434	https://hydro.ac/p/luogu-P1434	记忆化、二维网格、滑雪
◆ 拓展	luogu-P1002	https://hydro.ac/p/luogu-P1002	记忆化、过河卒
◆ 拓展	luogu-P1164	https://hydro.ac/p/luogu-P1164	记忆化、方案数计数
◆ 拓展	luogu-P1130	https://hydro.ac/p/luogu-P1130	记忆化、多阶段决策

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。从一维memo→二维memo→方案数计数，记忆化的三种memo模式。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1464	https://hydro.ac/p/luogu-P1464	三维memo、记忆化框架
◆ 拓展	luogu-P1028	https://hydro.ac/p/luogu-P1028	记忆化递推、递归→DP
◆ 拓展	luogu-P1044	https://hydro.ac/p/luogu-P1044	记忆化、卡特兰数
◆ 拓展	luogu-P1434	https://hydro.ac/p/luogu-P1434	记忆化、二维网格、滑雪
◆ 拓展	luogu-P1002	https://hydro.ac/p/luogu-P1002	记忆化、过河卒
◆ 拓展	luogu-P1164	https://hydro.ac/p/luogu-P1164	记忆化、方案数计数
◆ 拓展	luogu-P1130	https://hydro.ac/p/luogu-P1130	记忆化、多阶段决策

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能识别纯递归中的重复计算
[ ] 我能写出带 memo 数组的记忆化搜索框架
[ ] 我知道"未计算标记"该怎么选
[ ] 我能用记忆化解决网格路径和数字三角形
[ ] 我理解记忆化搜索和自底向上 DP 的关系
[ ] 我知道记忆化搜索的局限性（递归深度大时可能栈溢出）

🚀 下章预告：递归深潜到此结束！接下来我们要进入一个看似简单却充满陷阱的领域——二分查找。你玩过"猜数字"游戏吗？从 1 到 1000 里猜一个数，每次猜完对方告诉你"大了"还是"小了"。聪明的人最多 10 次就能猜中——这就是二分的力量。第 46 章见！🔍

第 45 章 记忆化搜索——让递归飞起来 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

45.1 重复计算有多可怕 ​

45.2 记忆化数组：算过就存 ​

45.3 记忆化搜索标准框架 ​

45.4 网格路径问题 ​

45.5 数字三角形 ​

45.6 记忆化 → DP 的桥梁 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1："未计算"标记选错了 ​

错 2：忘记初始化 memo 数组 ​

错 3：记忆化和递归参数不匹配 ​

错 4：忘记 return 记忆化结果 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​