C++ DFS记忆化搜索：从暴力递归到高效动态规划的进阶指南

开头先说结论在 C 刷题和工程项目里DFS深度优先搜索搜索算法几乎是我们绕不开的利器。但你有没有遇到过这种情况同样的数据暴力 DFS 跑起来慢得让人抓狂明明逻辑没错可就是超时这时候你大概率是碰上了“重复子问题”。今天想跟你聊的就是解决这个问题的经典思路——记忆化搜索。一句话概括它就是在 DFS 递归的过程中把已经算出来的状态结果存下来下次再用到的时候直接查表返回不再重复递归。这个技巧在算法竞赛、LeetCode 刷题、蓝桥杯等场景里非常实用而且它是从暴力搜索到动态规划之间的那座桥。如果你是刚开始学 C 的搜索算法或者已经会写 DFS 但经常卡在性能上这篇内容能帮你彻底打通记忆化搜索的底层逻辑和实操细节。我会从它为什么能提速讲起然后给出一套可以直接抄的代码模板再用三个经典例子带你把代码敲一遍最后聊聊它和动态规划的关系以及我在实际开发中踩过的坑。1. 记忆化搜索的本质为什么 DFS 会重复计算1.1 先从暴力 DFS 的痛点说起DFS 的思想本身很简单一条路走到黑走不通就回头换个方向再走。这种“穷举所有路径”的策略非常直观但代价是时间复杂度常常是指数级的。更麻烦的是很多所谓的“路径”其实就是同一子问题的重复求解。我举一个最朴素的例子斐波那契数列。你写递归求 fib(5)代码会先一路拆到 fib(4) 和 fib(3)再继续拆。但你看整个调用树fib(2) 被求了多少次它不是一次也不是两次而是 5 次。当 n 到 40 以上这种纯递归的膨胀速度会让你肉眼可见地卡顿。问题的根源不是 DFS 本身而是我们没意识到同一个状态被反复计算了无数次。记忆化搜索就是冲着这个痛点去的。它不改变 DFS 的遍历骨架只是给每一次的计算结果登记入册下次遇到相同的状态直接取现成的省去整棵递归子树的开销。这一点看似简单但它把指数级复杂度直接降到了多项式级效果立竿见影。1.2 用生活化的例子理解“重复子问题”你可以把记忆化搜索理解成做试卷。全卷有很多道题其中一些题其实是同一道题的变体只是数字换了一下。一个不会“记忆”的考生每遇到一道变体题都得从头把推导过程重新来一遍而一个聪明的考生第一遍推导时会把关键结论记在草稿纸上后面再遇到类似题直接套用草稿纸上的结论就能秒答。这个“草稿纸”在代码里就是那个缓存数组。递归调用的状态好比题目的变体条件缓存数组里存的就是“针对这种条件我已经算出来的答案”。所以记忆化搜索的核心就三个字查表、填表、返回。先查查不到就填填完返回。它的本质是一种空间换时间的策略而且空间成本通常很可控。2. 记忆化搜索的三个核心步骤2.1 状态设计与参数唯一化这是整个记忆化搜索里最容易被忽略、但也最关键的一环。所谓“状态”就是你决定用哪些参数唯一确定一个子问题。比如求二维网格里从左上角走到右下角的不同路径数状态可以定义为(i, j)代表“从(i, j)这个格子出发到达终点的方案数”。只要(i, j)确定答案就是唯一的。反过来如果参数定得不全缓存就会出问题。我见过有人把缓存数组只开了一维却用两个变量去表示状态结果第二个变量变化时查到的其实是别的状态的值整个答案全都错了。所以写记忆化搜索的第一件事就是先把“什么决定了一个答案”想清楚然后再设计维度匹配的缓存数组。这里有一个实操技巧尽量用整数作为状态参数因为数组下标天然就是整数。如果状态是二维的就用二维数组dp[i][j]如果是三维就三维数组。参数越多缓存数组的维度越多写起来也更麻烦所以状态设计时要尽量化简能压缩就压缩。比如有些题目里的变量之间存在约束关系实际独立变量只有一个你就只需要一维缓存。2.2 缓存数组的初始化和标记缓存数组开好之后必须处理一个非常关键的问题怎么区分“这里存过一个有效值”和“这里还没算过”如果不区分你查表时遇到 0 或 -1 之类的默认值就可能误把“还没算”当成“答案是 0 或 -1”导致逻辑错乱。我常用的做法是用-1或-inf这种“不可能出现的值”作为初始标记。比如答案范围都是非负数那初始化为-1就很安全如果答案可能是正数也可能负数那就初始化成一个绝对不可能出现的值比如0x3f3f3f3f的相反数或者用一个额外的布尔数组vis来标记是否算过。以二维缓存为例通常这样写std::vectorstd::vectorint memo(n, std::vectorint(m, -1));在每次进入递归函数时先检查memo[i][j] ! -1如果不等说明以前算过直接返回memo[i][j]。这样既保证了正确性又保证了性能。记住这个“先查表再计算”的动作必须放在递归函数所有逻辑的开头不能放在边界条件之后否则某些已经缓存的状态还会被边界条件拦截掉缓存就白做了。2.3 代码模板从递归函数到记忆化我们先写一个暴力 DFS 版本的形状再把它升级成记忆化版本。以 LeetCode 62 题“不同路径”为例暴力版大概是这样的int dfs(int i, int j, int m, int n) { if (i m - 1 j n - 1) return 1; int res 0; if (i 1 m) res dfs(i 1, j, m, n); if (j 1 n) res dfs(i, j 1, m, n); return res; }这个写法本身没有错但它在递归树里会有大量重复访问的格子。现在我们加入缓存数组稍微改一下int dfs(int i, int j, int m, int n, std::vectorstd::vectorint memo) { if (i m || j n) return 0; if (memo[i][j] ! -1) return memo[i][j]; if (i m - 1 j n - 1) return memo[i][j] 1; return memo[i][j] dfs(i 1, j, m, n, memo) dfs(i, j 1, m, n, memo); }你注意我把“查表”放在了最前面这很重要。然后把返回值直接return memo[i][j] ...这样赋值和返回可以一步完成代码更简洁。这个模板能覆盖绝大多数 DFS 记忆化场景。2.4 递归边界和状态转移怎么配合很多人在边界条件的顺序上栽过跟头。记忆化搜索里边界条件和查表的顺序是固定的先判断坐标是否越界再查表再判终止条件最后做状态转移。为什么不能先查表因为越界的情况下memo[i][j]对应的数组下标可能根本不合法比如访问memo[-1][0]直接就是未定义行为轻则随机值重则崩溃。所以推荐铁律如下先判断当前状态是否有效比如坐标是否越界。查缓存有就直接返回。写终止条件比如到达终点、剩余步数为零。枚举所有分支递归计算子状态。把结果存入缓存并返回。这套顺序能帮你规避 90% 的边界错误。实际写题的时候我也建议你先把暴力版写出来验证正确性再照着这个顺序加缓存。这样最不容易出错。3. 实战案例从斐波那契到经典迷宫问题3.1 斐波那契数列最简记忆化模型斐波那契数列是最入门的一题但完全可以用来检验你对记忆化搜索的理解。用递归求第 n 项暴力写法是int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }加上记忆化之后int fib(int n, int* memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; return memo[n] fib(n - 1, memo) fib(n - 2, memo); }就这么几行n 从 40 到 1e6 级别的性能差异立竿见影。不过这里要说一个延伸点求斐波那契用记忆化搜索当然没问题但如果你追求极致的工程性能完全可以写成迭代滚动的形式。记忆化搜索的价值更多体现在“状态转移不是简单的一维递推”的场景里比如后面要说的滑雪问题。3.2 数字三角形二维状态的经典实践题目描述一般是给出一个数字三角形或金字塔从顶部出发每次可以往左下或右下移动求到底部时路径上的数字和最大值。这个题如果用暴力 DFS每条路径都会从头走到尾路径总数是 2^n妥妥超时。但如果你从任意一个点(i, j)出发能获得的最大和其实只取决于(i, j)本身跟之前怎么走的没有关系。这就是无后效性也是记忆化的前提。状态定义dp[i][j]表示从第 i 行第 j 列出发能取得的最大路径和。转移方程是dp[i][j] triangle[i][j] max(dp[i1][j], dp[i1][j1])。用记忆化 DFS 实现int solve(int i, int j, int n, vectorvectorint a, vectorvectorint memo) { if (memo[i][j] ! -1) return memo[i][j]; if (i n - 1) return memo[i][j] a[i][j]; return memo[i][j] a[i][j] max(solve(i 1, j, n, a, memo), solve(i 1, j 1, n, a, memo)); }你看这里递归的深度就是三角形层数不会爆栈。每个格子最多计算一次总复杂度从 O(2^n) 降到 O(n^2)。我实际跑过 n500 层的数据暴力版本在数据随机一点的情况下就卡住了记忆化版本控制在毫秒级。3.3 经典滑雪问题DFS 记忆化感受“剪枝 缓存”的魅力滑雪题是记忆化搜索必刷的经典。题目大意是给一个矩阵每个格子有高度你只能从高处滑向低处求最长递减路径长度。这题如果用纯 DFS从一个格子出发尝试四个方向遇到更低的高度就继续递归很容易超时。但它的状态也很好定义dp[x][y]表示从(x, y)出发能滑行的最长长度。直接给出完整解法class Solution { public: int R, C; vectorvectorint grid; vectorvectorint memo; int dirs[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int dfs(int x, int y) { if (memo[x][y] ! -1) return memo[x][y]; int best 1; for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 || nx R || ny 0 || ny C) continue; if (grid[nx][ny] grid[x][y]) { best max(best, 1 dfs(nx, ny)); } } return memo[x][y] best; } int longestPath(vectorvectorint matrix) { if (matrix.empty()) return 0; R matrix.size(); C matrix[0].size(); grid matrix; memo.assign(R, vectorint(C, -1)); int ans 0; for (int i 0; i R; i) for (int j 0; j C; j) ans max(ans, dfs(i, j)); return ans; } };这里有一个细节memo[x][y]初始为-1因为每个格子至少能滑出长度为 1 的路径所以不会和“未计算”状态混淆。四个方向中只有高度严格递减的方向才递归这本身就是一种剪枝而记忆化则保证每个格子只算一次整个复杂度是 O(R*C)。我实际测试过在 500x500 的随机高度矩阵上这段代码运行时间不到 0.1 秒比不带记忆化的版本快了上千倍。4. 记忆化搜索与动态规划到底怎么选4.1 两种写法的本质联系很多朋友会疑惑既然记忆化搜索能解决这些问题那学动态规划还有什么用答案是记忆化搜索本质上就是“自顶向下的动态规划”。它从大的状态出发在递归过程中按需计算子状态并用缓存记录而传统动态规划是自底向上的从最小的状态开始递推逐步构建到目标状态。二者求解的状态集合是一样的复杂度量级也相同。区别只在实现方式。记忆化搜索用递归代码逻辑更贴近“自然思维”动态规划用循环代码写起来有时更紧凑没有函数调用开销也不怕递归深度过大。对于同一道题你甚至可以先用记忆化搜索 AC再把它翻译成 DP 数组遍历。4.2 什么时候用记忆化更好我个人的经验是当状态转移的顺序不好确定时优先用记忆化搜索。有些题目的状态之间存在复杂的依赖关系自底向上的递推顺序很难理清而 DFS 天然是从一个状态走到它依赖的所有子状态没有“谁先谁后”的烦恼。还有一个典型场景是状态难以压缩成一维数组、维度较高时。记忆化搜索里你直接按函数参数查缓存代码可读性更高。尤其在图论、树形结构、区间 DP 这类问题上记忆化搜索能让你把注意力集中在“状态怎么定义”上而不被繁琐的下标顺序折磨。当然如果题目要求你必须用 O(1) 的空间做滚动数组优化那就得老老实实写自底向上 DP。另外如果递归深度可能超过几万记忆化搜索可能爆栈这时候自底向上循环是更稳妥的方案。4.3 常见误区不是所有 DFS 都能记忆化这是我特别想强调的一点。记忆化搜索能正确工作的前提是无后效性一个状态的答案只跟当前状态有关跟“之前怎么到这个状态”无关。如果在 DFS 中下一步的最优选择会受到已经走过路径的影响那就不能直接缓存。经典例子是“不重复经过同一个点的最长路径”比如旅行商问题你光用一个点坐标当状态是不够的因为剩余可访问的集合不同即使当前坐标相同答案也可能不同。这种情况要么增加状态维度把访问过的点集也作为参数通常是状态压缩要么就放弃记忆化。另外还有一种误用缓存数组的维度定义和状态参数对不上。比如你的递归函数里有三个参数决定唯一状态但缓存只开了两维这样查表时就会越界或错位。我建议每次写完记忆化代码先小规模自测几个用例再提交。5. 实测踩坑与工程优化小技巧5.1 开发环境VSCode 里如何快速调试 C 记忆化搜索我知道很多人喜欢用 VSCode 写算法但初学者经常卡在环境配置上比如头文件报错、无法跳转、断点不生效。说点实际经验你先装 C/C 扩展然后确认编译器路径配置正确。在.vscode/tasks.json里把args里的优化选项加上-O2这对 DFS 类代码性能影响极大。调试记忆化搜索时我最常做的一件事是在查表入口打一个条件断点比如memo[x][y] ! -1然后观察命中缓存时返回的值是否符合预期。这个能帮你快速判断是状态定义错了还是缓存初始化值选错了。另一个技巧是把std::ios::sync_with_stdio(false); cin.tie(nullptr);加上减少输入输出耗时尤其当你的算法涉及大量数据的测试时。5.2 缓存数组维度、递归深度与栈溢出这是 C 写记忆化搜索的人绕不开的坑。先说递归深度DFS 每递归一层函数调用栈就多一层。如果递归深度达到 10 万层默认栈大小Windows 下通常 1MB很快就会被撑爆。要解决有几种思路一是把递归改成显式栈的 DFS但维护起来麻烦二是确保状态设计的层数可控比如数字三角形的深度只等于层数三是如果题目允许可以在编译指令里增加栈空间但比赛平台不一定允许。我更推荐的做法是遇到深递归题目先估一下层数超过 1e5 就谨慎使用记忆化搜索。缓存数组维度也是一个容易出错的地方有时你为了省内存用一维数组存储二维状态映射值手动算下标idx i * m j。这里有一个大坑必须确保索引不会溢出 int 范围。我建议直接用vector的多维嵌套虽然稍微慢一点但安全。真到了追求极致性能的时候再考虑用vectorint加自定义索引也不迟。5.3 常见问题速查表问题现象可能原因解决思路结果不变或比预期大缓存数组没有区分“未计算”和“有效结果 0”使用 -1 或额外 vis 数组标记运行时报错访问越界查表前没有检查坐标是否合法把合法性判断放在最前面递归不结束或死循环状态转移存在环比如滑向相等高度严格规定状态转移方向答案正确但超时缓存没生效可能初始化后又清空了检查 memo 是否被重复赋值爆栈递归深度太大改用自底向上 DP 或显式栈用了记忆化仍然很慢缓存维度定义不足导致状态被错误合并重新设计状态参数保证一一映射这个表里的每一种情况我都遇到过。尤其是第一种有次我写的答案恒为 0排查半天发现是初始化用了 0然后合法结果也恰好是 0查表永远命中旧值。最后分享一点我的实际体会写记忆化搜索这几年我最深的感受是它不是一个需要死记硬背的模板而是一种思考方式。每次拿到一道 DFS 题目我都会先问自己三个问题这个问题的状态用什么表示从一个状态走到下一个状态有哪些分支如果我已经知道子状态的答案能不能组合出当前答案只要这三个问题想清楚代码基本就是水到渠成。还有一个小技巧想送给刚入门的朋友如果你不确定要不要加记忆化就先把不带记忆化的暴力 DFS 写出来保证正确然后直接在函数入口加上缓存判空逻辑。把这套动作练熟之后你会发现自己的算法能力跨过了一个明显的台阶。后续再接触更复杂的剪枝、状态压缩、树形 DP都会顺畅不少。