← 目录 / 算法文档 · 模块十二 搜索基础 / 12.4 记忆化搜索

12.4　记忆化搜索

不同的搜索路径，可能会绕到完全相同的状态——把算过的状态缓存起来，下次直接查表，不用再重新展开一次搜索。

本页目录
① 从"剪枝"到"记忆化"：另一种浪费

12.3 节的剪枝解决的是：一条分支还没走到底，就已经能看出走不通，于是提前放弃，省下后面白费的递归。本节要解决的是另一种、更隐蔽的浪费：有些分支各自看起来都合法，会一路正常地递归下去——但走着走着，两条完全不同的分支可能会殊途同归，绕到了完全相同的一个"状态"上，而代码并不知道这一点，于是把这个状态从头到尾又重新搜索了一遍。

8.2 节已经用斐波那契数列演出过这个思路：fib(4) 展开成一棵树后，fib(2) 被不同的分支各算了一次；解决办法是把算过的结果存起来，下次查表直接用，不重新递归，这就是记忆化（Memoization）。但斐波那契毕竟只是一条简单的线性递推，状态空间也就是一个数字 n。本节要把同样的思路用到真正的搜索问题上——状态不再是一个简单的数字，而是像"网格里的一个格子"这样更复杂的东西，搜索的方式也是 DFS，和 12.1～12.3 节一脉相承。

② 引例：滑雪——网格里最长的下降路径

给定一个 R×C 的网格，每个格子有一个高度值。可以从当前格子滑向上下左右相邻的格子，但只能往严格更低的地方滑（目标格子的高度必须比当前格子小）。问：整个网格里，能滑的最长路径（经过的格子数）是多少？——这是信息学竞赛里"记忆化搜索"最经典的入门题（滑雪问题）。

用一个 3×3 的小网格来演示：

网格高度
9
8
7
6
5
4
3
2
1
高亮的一条路径：9→6→5→4→1（下、右、右、下），每一步都严格变小，一共 5 个格子
这条路径就是整个网格里的最长下降路径，长度是 5。定义 dfs(i,j) 表示"从格子 (i,j) 出发，能滑的最长路径有多少个格子"——整个网格的答案，就是所有格子的 dfs(i,j) 中的最大值。dfs(i,j) 天然满足递归关系：dfs(i,j) = 1 + max{ dfs(相邻且更低的格子) }，如果四周没有比它更低的格子，dfs(i,j) = 1（滑到这里就停了）。
③ 朴素 DFS：不同起点会重复展开同一个状态

最直接的想法：对每个格子都调用一次 dfs(i,j)，取所有结果里的最大值。dfs 本身就是一次 DFS——从 (i,j) 出发，往四个方向试探，只要相邻格子更低就递归下去，四个方向都不能走时返回 1。

C++ · 朴素 DFS（没有记忆化）
1int h[55][55]; // 网格高度
2int R, C;
3int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1}; // 上下左右
4
5int dfs(int i, int j) // 从 (i,j) 出发能滑的最长路径
6{
7 int best = 1; // 至少能"滑"这一个格子本身
8 for (int k = 0; k < 4; k++)
9 {
10 int ni = i + dx[k], nj = j + dy[k];
11 if (ni < 0 || ni >= R || nj < 0 || nj >= C) { continue; } // 出界
12 if (h[ni][nj] >= h[i][j]) { continue; } // 没有更低，不能滑
13 best = max(best, 1 + dfs(ni, nj)); // ★ 每次都重新递归，即使 (ni,nj) 之前算过
14 }
15 return best;
16}

问题出在第 13 行：从不同格子出发的搜索，很可能会绕到同一个格子。以刚才的 3×3 网格为例，格子 (1,1)=5 既能从 (0,1)=8 往下滑到达，也能从 (1,0)=6 往右滑到达——两条完全不同的搜索分支，都会各自调用一次 dfs(1,1)，把"从 5 出发还能滑多远"这件事重新搜索一遍：

分支 A：从 (0,1)=8 出发
9
8
7
6
5
4
3
2
1
8 → 5 → 4 → 1
分支 B：从 (1,0)=6 出发
9
8
7
6
5
4
3
2
1
6 → 5 → 4 → 1
(1,1)=5 这个格子（粉色）在两条分支里都被当作起点重新搜索了一次——两次调用 dfs(1,1) 算出的答案完全相同（都是从 5 出发能滑 3 个格子：5→4→1）。网格越大，这种"殊途同归"的情况会越来越多，朴素 DFS 的调用次数会随格子数指数级增长。
④ 加上记忆化：每个状态只算一次

解决办法和 8.2 节一样：用一个数组把每个状态的答案缓存起来，进入 dfs(i,j) 时先查表，如果这个格子已经算过，直接返回缓存的结果，不再重新展开搜索。这里的"状态"是二维的 (i,j)，所以缓存数组也开成二维。

C++ · 记忆化 DFS
1int dp[55][55]; // 记忆表：dp[i][j] 表示 dfs(i,j) 是否已经算过、算出的值是多少
2
3int dfs(int i, int j)
4{
5 if (dp[i][j] != -1) { return dp[i][j]; } // ✅ 查表：算过就直接返回，不再往下搜索
6 int best = 1;
7 for (int k = 0; k < 4; k++)
8 {
9 int ni = i + dx[k], nj = j + dy[k];
10 if (ni < 0 || ni >= R || nj < 0 || nj >= C) { continue; }
11 if (h[ni][nj] >= h[i][j]) { continue; }
12 best = max(best, 1 + dfs(ni, nj));
13 }
14 return dp[i][j] = best; // ✅ 存表：算完顺手存起来，再返回
15}
💡
只改了两行，但效果天差地别：第 5 行在搜索之前先查表——分支 B 调用 dfs(1,1) 时，如果分支 A 已经算过并存进了 dp[1][1]，就直接把结果拿来用，连四个方向的 for 循环都不会执行。第 14 行把"返回"和"存表"合并成一行：算出 best 之后，先赋值给 dp[i][j]，同一个表达式的值又是这次要返回的结果，一举两得。
⑤ 完整代码与复杂度对比

加上读入数据和主函数，对每个格子调用一次 dfs，取所有结果里的最大值：

C++ · 滑雪问题完整代码
1#include <iostream>
2#include <cstring>
3using namespace std;
4
5int h[55][55], dp[55][55], R, C;
6int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
7
8int dfs(int i, int j)
9{
10 if (dp[i][j] != -1) { return dp[i][j]; }
11 int best = 1;
12 for (int k = 0; k < 4; k++)
13 {
14 int ni = i + dx[k], nj = j + dy[k];
15 if (ni < 0 || ni >= R || nj < 0 || nj >= C) { continue; }
16 if (h[ni][nj] >= h[i][j]) { continue; }
17 best = max(best, 1 + dfs(ni, nj));
18 }
19 return dp[i][j] = best;
20}
21
22int main()
23{
24 cin >> R >> C;
25 for (int i = 0; i < R; i++)
26 for (int j = 0; j < C; j++) cin >> h[i][j];
27 memset(dp, -1, sizeof(dp)); // ★ 全部初始化成 -1，表示"还没算过"
28
29 int ans = 0;
30 for (int i = 0; i < R; i++)
31 for (int j = 0; j < C; j++)
32 ans = max(ans, dfs(i, j)); // 每个格子都可能是最长路径的起点
33
34 cout << ans << endl;
35}
写法每个状态被计算的次数时间复杂度
③ 朴素 DFS可能被多条分支重复计算，最坏情况下随格子数指数增长最坏 O(2^(R×C)) 级别
④⑤ 记忆化 DFS每个状态只计算一次，之后全部查表O(R×C)（状态数）× O(4)（每个状态的转移）
🎯
记忆化搜索的效率提升，本质和 8.2 节的斐波那契一模一样：状态总数是固定的（这里是 R×C 个格子），只要保证每个状态只被真正计算一次，总时间就等于"状态数 × 每个状态的转移开销"。朴素 DFS 之所以慢，不是因为搜索方式错了，而是同一个状态被反复当成"新问题"从头搜索；记忆化搜索的代码结构和朴素 DFS 几乎一样，只是多了"查表"和"存表"这两步。
⑥ 适用条件与常见陷阱

并不是所有 DFS 都能直接套上记忆化，需要满足两个条件：

条件在滑雪问题里对应什么
① 状态能被清晰地定义、编号用 (i,j) 这一对坐标就能唯一确定一个状态，可以直接当数组下标
② 状态转移无后效性（不能有环）只能往严格更低的格子滑——高度值只减不增，保证不会滑回原来的格子，状态之间不会形成循环依赖
⚠
用 0 表示"还没算过"，却忘了 0 也可能是合法答案：本节用 -1 初始化 dp 数组，就是因为最短路径长度也可能是一些边界情况下的合法值。如果偷懒直接把数组默认初始化为 0，一旦某个状态的正确答案恰好是 0，就会被误判成"没算过"而重复计算；反过来，如果某个状态还没算过，却被误当成"已经算出 0"直接返回，答案就错了。养成习惯：初始化用一个不可能是合法答案的值（比如 -1），或者干脆用一个额外的 bool visited[][] 数组专门记录"是否算过"。
⚠
状态转移里存在环，记忆化会死循环：如果去掉"严格更低"这个限制、允许滑向高度相等或更高的格子，两个格子就可能互相依赖（dfs(A) 需要 dfs(B)，dfs(B) 又需要 dfs(A)），递归永远无法触底，直接栈溢出。记忆化搜索能生效的前提，是状态之间的依赖关系构成一张有向无环图（DAG）——本题正是靠"严格递减"这个条件天然保证了不会成环。
⚠
记忆表开的位置或大小不对：dp 数组要开在全局（或用 static），不能开在 dfs 函数内部当局部变量——否则每次调用都会重新创建一份空的记忆表，等于完全没有缓存效果。数组大小也要按题目给定的最大范围开够，避免越界。
🏆
模块小结与展望：12.1～12.4 节走完了一条完整的路：DFS（暴力搜索所有可能）→ 回溯（用"做选择/撤销选择"规范地遍历分支）→ 剪枝（提前放弃不合法的分支）→ 记忆化（缓存重复出现的状态，避免同一个状态被反复搜索）。记忆化搜索还有一个更重要的身份——它本质上就是"自顶向下"的动态规划：从大问题出发，递归拆解成小问题，用缓存避免重复计算。下一模块（13 动态规划基础）要学的，是同一件事的"自底向上"写法——不用递归，而是按顺序把小问题的答案先算出来，再逐步推导出大问题的答案。两种写法能解决同一类问题，各有优势，值得对照着学。