一说起算法竞赛里的搜索，大多数人的第一反应就是DFS/BFS、回溯、剪枝。可等你真正开始刷题就会遇到一个很尴尬的问题：剪枝剪得再狠，该超时的题还是超时；递归写得再漂亮，数据一大照样TLE。原因往往就藏在"重复子问题"四个字里。而解决重复子问题最直接的工具，就是记忆化搜索。
这篇内容是我给算法竞赛集训队讲基础课时的讲义整理版，主题非常明确：弄清记忆化搜索到底是什么、为什么它能把指数级复杂度拽下来、什么时候该用它、以及考场上最常见的几个致命坑。不管你是准备蓝桥杯、ICPC、CCPC，还是刚起步学算法的新手，这篇都值得从头看到尾。
1. 不记账的DFS：一样的递归，差出几个数量级的调用量
1.1 从一个最普通的搜索框架讲起
先回忆一下最朴素的DFS长什么样。以经典的二叉树路径求和为例，你要从根节点走到叶子节点，求满足某种条件的路径条数。通常写法是：
int dfs(TreeNode* node, int sum) { if (!node) return 0; sum += node->val; if (!node->left && !node->right) { return (sum == target) ? 1 : 0; } return dfs(node->left, sum) + dfs(node->right, sum); }这个框架非常典型：从当前状态出发，枚举所有可能走向，递归求解子问题，最后把子问题的结果合并。它的核心假设是——每个子问题都是独立的，都必须亲自从头算一遍。
但竞赛题目里，很多时候子问题并不独立。我举个例子你就明白了：计算斐波那契数列第n项。
int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }你算过fib(40)耗时多少吗？在我电脑上大约要1秒多。fib(50)？跑完估计得等将近一小时。但同样的fib(50)，如果用记忆化搜索，瞬间出结果，快得连计时器都显示不出来。
差在哪？就在重复调用。
1.2 指数爆炸的根因：重复子问题
我们把fib(5)的递归调用树展开：
- fib(5) 调 fib(4) 和 fib(3)
- fib(4) 调 fib(3) 和 fib(2)
- fib(3) 调 fib(2) 和 fib(1)
注意，fib(3)被调用了两次，fib(2)被调用了三次。每一层的重复都会往下传导，于是调用次数呈指数增长。fib(n)的调用次数本身就是指数级别的。
这类问题的共同特征就是重复子问题：同一个状态（参数组合）会在递归过程中反复出现，而且每次出现的计算结果完全一样。既然结果一样，为什么还要重复算？
朴素DFS的问题在于"不记账"。它像一个没有备忘录的项目经理，每个任务都从零开始推演，完全忘了昨天刚刚算过同样的东西。搜索框架本身没错，错的是没有缓存中间结果。
1.3 剪枝救不了这种超时
很多初学者第一反应是"那我加剪枝"。剪枝确实有用，但它解决的是另一类问题。
剪枝的核心逻辑是：提前判断某个分支不可能产生答案，直接跳过，从而减少状态数。比如在迷宫搜索里，发现当前位置离终点太远、剩余步数不够，就不再往下走。
但重复子问题不属于"不可能的分支"，它属于"一定会被反复访问的分支"。剪枝剪不掉重复计算，因为每条路径都合法，都需要探索。你就算把分支剪得再干净，fib(3)该算两次还是算两次。
这也是我想强调的第一点：看到超时先别急着上剪枝，先判断有没有重复子问题。有重复子问题，记忆化是第一优先级；没有重复子问题，才轮到考虑剪枝。
2. 记忆化搜索的标准写法：状态参数加缓存，缺一不可
2.1 状态设计的三条原则
要把DFS改造成记忆化搜索，不是简单加一个数组就行。你得先想清楚"状态"是什么。
记忆化搜索里的状态，指的是能够唯一决定递归结果的参数组合。在fib里，状态就是n；在二叉树路径里，状态就是(node, sum)；在迷宫里，状态就是(i, j, step)。
设计状态时记住三条原则：
- 参数必须能唯一确定一个递归结果。如果两个不同状态的结果可能不同，那它们就不能混用缓存。
- 参数要尽量少。状态维度越少，缓存数组越省空间，命中率也越高。
- 参数之间要有明确的层递关系。通常是从大状态递归到小状态，保证不会出现循环依赖。
很多人写记忆化搜索翻车，根源就在第一条。比如在迷宫问题里，如果只拿(i, j)当状态，忽略了剩余步数step，那就出大问题了——同一个位置在剩余步数不同时，可走的路径数量天差地别。把这两者混进同一个缓存条目，结果必错。
2.2 备忘录的形状与初始化
备忘录可以用数组、二维数组、哈希表，取决于状态维度。
- 一维状态用一维数组，例如
int memo[N] - 二维状态用二维数组，例如
int memo[N][M] - 状态维度多、且取值范围稀疏时，用哈希表
map<pair<int,int>, int>
判断一个子问题是否已计算，一般靠一个"未访问标志"。竞赛里最常用的是把备忘录全部初始化为-1，因为绝大多数题目的合法结果都是非负数。
int memo[N]; memset(memo, -1, sizeof(memo)); int dfs(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; return memo[n] = dfs(n - 1) + dfs(n - 2); }这个写法有三个关键动作：
memset(memo, -1, sizeof(memo))把缓存全部标记为"未计算"- 递归开始先查缓存，命中就直接返回
- 计算结果存进缓存再返回
2.3 记忆化搜索的通用模板
把上面套路抽象一下，就得到一套几乎通用的记忆化框架：
// 备忘录定义与初始化省略 int dfs(State s) { if (isBase(s)) return baseAnswer(s); // 递归边界 if (memo[s] != UNVISITED) return memo[s]; // 缓存命中 int ans = worstPosssibleValue; // 根据题意设定 for (auto& next : transition(s)) { // 枚举状态转移 ans = better(ans, dfs(next)); } return memo[s] = ans; }模板核心就四步：判边界、查缓存、做转移、存缓存。后面所有记忆化搜索的题，都是对这四个步骤的变体。
我个人强烈建议把这个模板练到条件反射。因为比赛现场是没有时间让你慢慢推演递归流程的，肌肉记忆才是最快的解题路径。
3. 三题拆解：从入门题到国奖题，记忆化是怎么一步步发力的
3.1 数字金字塔：把DFS直接升级成记忆化
题目长这样：给出一个数字金字塔，从顶层到底层，每次可以走左下或右下，求路径上的数字和最大值。
先写朴素DFS：
int a[N][N]; int n; int dfs(int i, int j) { if (i == n) return a[i][j]; return a[i][j] + max(dfs(i + 1, j), dfs(i + 1, j + 1)); }这个代码逻辑完全正确。但如果n=500，它会被卡得怀疑人生。因为从顶点到某个中间节点，路径数量是组合数级别，而这个组合数会随着层数指数增长。
问题就在dfs(i+1, j)和dfs(i+1, j+1)会反复访问同一个(i, j)，每个(i, j)又被无数上层路径重复调用。
加上记忆化：
int memo[N][N]; memset(memo, -1, sizeof(memo)); 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)); }只改了三行代码，复杂度从O(2^n)降到O(n²)。状态数从指数变成n层乘n列，每个状态只算一次。
这个例子我每次讲都会强调：它证明了记忆化不是一种"高级优化"，而是把搜索从不可用变成可用的关键手段。
3.2 过河卒：障碍物下的路径计数
经典题目。棋盘上有障碍物，卒从(0,0)走到(m,n)，只能向下或向右，求路径条数。
朴素DFS同样是重复计算爆炸：同一个格子在多条不同路径里会被多次访问。
写记忆化版本：
long long memo[m+1][n+1]; memset(memo, -1, sizeof(memo)); long long dfs(int x, int y) { if (x < 0 || y < 0) return 0; if (x == 0 && y == 0) return 1; if (memo[x][y] != -1) return memo[x][y]; if (isForbidden(x, y)) return 0; return memo[x][y] = dfs(x - 1, y) + dfs(x, y - 1); }这里有个有意思的细节：isForbidden的判断放在缓存命中之后。为什么？
因为如果一个格子是障碍物，它的值永远为0。你先把这个0存进备忘录，后面所有路径访问它时直接返回0，省去再次判断障碍物的开销。虽然这个优化很小，但在m、n都是1000的极限数据下，它能省掉不少常数时间。
这类带障碍、带限制的路径计数题，是记忆化搜索最典型的应用场景。因为它天然存在大量重复子问题，而状态又很好设计，就是坐标本身。
3.3 滑雪问题：记忆化搜索的经典代表作
题目：给一个矩阵，每个格子有高度。你可以从任意格子出发，移动到高度严格递减的相邻格子。求最长能滑多远。
这题不能用递推DP直接做，因为并没有一个天然的顺序能保证先算"小的"状态。高度是乱序的，你没法像金字塔那样从下往上一步步推。
记忆化搜索就舒服了：
int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int memo[R][C]; memset(memo, -1, sizeof(memo)); int dfs(int x, int y) { if (memo[x][y] != -1) return memo[x][y]; int best = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; if (h[nx][ny] < h[x][y]) { best = max(best, dfs(nx, ny) + 1); } } return memo[x][y] = best; }每个格子的最长下滑距离，取决于它周围比它更低的格子。但由于高度无序，你不知道该先算谁。用记忆化搜索，递归天然地帮你解决了"计算顺序"问题。
很多学生问我：这题能用DP做吗？能做，但需要按高度从低到高排序，再逐个更新。逻辑反而绕。记忆化搜索直接按递归依赖走，思维负担小很多。
从这三道题能看出一个规律：当状态转移方向不确定、或依赖关系成环无序时，记忆化搜索的代码量和思维复杂度往往远低于递推DP。
4. 什么时候选记忆化搜索，什么时候必须写递推DP
4.1 记忆化搜索本质上就是带递归的DP
先说结论：记忆化搜索和递推动态规划在数学上是完全等价的关系。它们求解的状态集合一样，状态转移方程一样，复杂度也一样。
区别在于代码方向：
- 递推DP是从小状态向大状态推，先算基础状态，再逐步推导。
- 记忆化搜索是从大状态出发递归调用，让子问题先被算出，再静默地完成任务。
我做的对比图在验证时，常用下面这种速查表：
| 对比维度 | 记忆化搜索 | 递推DP |
|---|---|---|
| 思维方向 | 自顶向下，顺着依赖走 | 自底向上，按顺序推 |
| 代码可读性 | 贴近自然递归，易写 | 需要额外设计循环顺序 |
| 状态依赖复杂时 | 天然支持乱序依赖 | 需要拓扑排序或自定义顺序 |
| 递归深度大时 | 可能爆栈，需注意 | 无此问题 |
| 函数调用开销 | 略高 | 更快 |
4.2 最适合用记忆化搜索的两个场景
第一个场景是状态转移方向不好确定。就像前面滑雪题，自然依赖关系不是顺序的。如果你硬要用递推，就得先对所有状态排序，这一步本身就很容易出错。
第二个场景是状态空间稀疏。有些题状态维度高（比如三维、四维），但实际会访问到的状态只有一小部分。递推DP会把所有可能状态全算一遍，哪怕很多根本用不到。记忆化搜索是"用到才算"，在稀疏状态下能省掉大量无效计算。
举个真实比赛例子：有状态参数是坐标(x, y)加上一个掩码mask，但坐标组合只有少数合法。如果用递推，你得为整个(x, y, mask)三维空间开数组，其中九成空间都是浪费。记忆化搜索只填实际访问到的格子，时间和空间都更省。
4.3 最后一种情况：必须用递推DP
不能用记忆化搜索的情况也真实存在，最典型的是递归深度过深。
竞赛里常见的问题是n达到10^6级别的线性DP。比如最长上升子序列的O(n²)版本，如果写成递归记忆化，递归链长度可能到10^6，直接栈溢出。这种情况必须改写为递推。
另外，如果状态转移存在环（A依赖B、B又依赖A），记忆化搜索也会死循环，因为递归永远等不到子问题的结果。这类问题得靠其他技巧处理，记忆化就无能为力了。
所以我的建议是：两种写法都要熟练。遇到乱序依赖、稀疏状态时用记忆化；遇到大范围线性递推时用DP。不要有门派之见，最终目标都是把题做对做快。
5. 竞赛考场上最容易踩的三个坑
5.1 递归深度把栈压爆
这可能是记忆化搜索最尴尬的坑。代码逻辑全对，IDE里小数据测试也正常，一上大样例就段错误或者直接崩溃。
原因就是递归深度太大。C++默认栈空间八兆左右，递归层数一深，栈帧叠起来就会爆炸。
处理方法有几种：
- 用迭代DP改写。最推荐，但有时改写费劲。
- 手动扩大栈空间。有些OJ支持指令扩大栈，这在比赛中不一定稳妥。
- 改用自底向上的写法。即把记忆化搜索的递归逻辑手动改成循环加栈。
我建议，只要预测出递归深度可能超过10^5，就老老实实先想递推方案，别赌栈空间。
5.2 memo初始值选错，答案直接错乱
这是记忆化搜索里最隐蔽的错误之一。
初始值用-1的前提是合法结果中不包含-1。如果题目结果可能为-1（比如路径不存在时返回-1），那初始值就不能再用-1，否则会误判"已计算"。
更麻烦的情况是结果本身包含任意整数，包括-1。这时可以用一个标志数组单独表示是否已计算：
bool vis[N][M]; int memo[N][M]; int dfs(int x, int y) { if (vis[x][y]) return memo[x][y]; vis[x][y] = true; // 计算 memo[x][y] ... return memo[x][y]; }这种写法多开一个bool数组，但一劳永逸，不再受"结果取值范围"限制。
还有一种坑是初始化数组大小不够。状态参数范围比数组维度大，直接越界，这种错在OJ上报出来是Runtime Error，很容易让人一头雾水。
5.3 状态参数漏掉一个维度
前面提过迷宫例子，这里再展开讲透。
假设题目要求：从起点走到终点，最多还能踩k次特殊地板，求最短步数。你在写DFS时只用了(x, y)两个参数，没把k放进状态。那问题就大了——同一个位置(x, y)，在k=0和k=5的时候，能走的路径完全不一样。如果你把它们当作同一个状态存入缓存，第二次访问就可能拿到错误的"已计算"结果。
排查这类错误有一个技巧：问自己一句话——当前剩余的所有信息里，有没有哪一项会影响最终答案？影响答案的每一项，都必须是状态参数或者能从状态参数推出来的常量。漏了一项，缓存就是错的。
我见过太多参赛选手在这个坑里翻车，而且因为结果在个别测试点才出错，很难排查。经验就是：宁可多开一两个维度，也别少开一个维度。
6. 从记忆单点走向状态压缩：记忆化搜索的高阶玩法
6.1 当状态参数不是单个数字时
前面讨论的状态都是坐标、层数这类简单整数。但竞赛里常常出现更复杂的状态。例如旅行商问题（TSP）的变形：当前在城市u，已经访问过的城市集合是visited。
visited不是一个整数，而是一个集合。怎么把这个集合作为记忆化搜索的状态？答案是状态压缩——用一个二进制整数表示集合，第i位为1代表已访问城市i。
int dp[1 << n][n]; memset(dp, -1, sizeof(dp)); int dfs(int mask, int u) { if (mask == (1 << n) - 1) return dist[u][0]; if (dp[mask][u] != -1) return dp[mask][u]; int ans = INF; for (int v = 0; v < n; v++) if (!(mask & (1 << v))) { ans = min(ans, dist[u][v] + dfs(mask | (1 << v), v)); } return dp[mask][u] = ans; }这里面mask就是整个已访问集合的压缩表示。状态数量为2^n乘以n，在n=20以内基本可行。这也是"记忆化搜索+状态压缩"这一套组合拳在竞赛里最常见的使用场景。
6.2 记忆化配合剪枝，能快非常多
要说记忆化搜索的进阶，不能不提它与剪枝的组合使用。
前面我说过剪枝无法解决重复子问题，但剪枝在减少无效状态这一点上依然重要。两者组合后，搜索树会被大幅压缩：
- 剪枝负责把明显不可能的分支直接砍掉，减少状态的横向扩展。
- 记忆化负责把到达过的状态缓存起来，避免不同路径访问同一状态时的重复计算。
有一个常见技巧是优先级排序：先DFS那些最有可能产生最优解的分支。这样首个全局答案会尽量接近最优，后续剪枝会更激进。在记忆化搜索里，这个技巧同样适用。
6.3 调试记忆化搜索的三个实用技巧
最后分享一点我实战中常用的调试心得，这部分常规教材很少写。
第一个技巧是打印缓存命中率。在查缓存分支里加一个计数器，在存缓存分支加另一个计数器，两个数一比就能看出记忆化到底拦住了多少次重复计算。如果命中率接近0，说明状态设计有冗余或者根本不存在重复子问题。
第二个技巧是小数据暴力对拍。写一个不记忆化的朴素DFS作为基准，在小数据范围内随机生成测试用例，将两个函数的输出对比。我写记忆化搜索改动稍大时，必定会做这一步，能揪出绝大多数状态设计错误。
第三个技巧是检查递归出口是否有返回值。这个问题看起来低级，但真有很多人在递归边界里忘写return。尤其是状态分支多、边界条件复杂时，漏掉一个边界分支会导致未定义返回值，配上记忆化缓存，错得极其隐蔽。
这三个技巧是我带集训队时反复强调的内容。很多选手觉得记忆化搜索"懂了"，但一到手就出错。事实上，所谓懂了，不只是能写出正确代码，还包括能在出错时快速定位问题在哪。
回顾整条主线，记忆化搜索解决的核心问题就一个：不重复计算已经算过的东西。从最朴素的DFS到状态压缩记忆化，代码量没有本质变化，只是一层一层往"缓存"里塞了更多信息。它能让你在竞赛里写出更简单更稳的解法，也能帮你在状态依赖复杂的题目里节省大量思考时间。
如果你现在刚开始学算法竞赛，我的建议是先把数字金字塔和滑雪这两道题用记忆化搜索各写三遍，直到不查模板就能流畅写出完整代码。然后再去尝试带状态压缩的TSP类问题，感受一下"搜索+缓存"能到达的高度。这条路走通了，"搜索"这一章你就真正入门了。
