LeetCode 329 最长递增路径：C++ DFS+记忆化搜索详解-北京尧图网络

1. 先把这个题看透题意、本质和常见误区LeetCode 329 这道题我在面试里见过也在刷题群里看人争论过。题目输入是一个二维整数矩阵要求返回矩阵中最长递增路径的长度C 接口签名是int longestIncreasingPath(vectorvectorint matrix)入口参数就是一个标准vector二维容器。题目看起来很短但真正动手写的时候很多人在 DFS 和 DP 之间摇摆不定写出来的代码要么超时要么边界翻车。今天我用 C 把它完整拆一遍从状态定义到记忆化搜索再到实际跑数据踩过的坑一次性说清楚。1.1 题目到底在问什么题目给的是一个m x n的整数矩阵matrix要求返回矩阵中最长递增路径的长度。注意几个关键约束路径只能从当前格子往上下左右四个方向移动不能斜着走也不能越界路径上的值必须严格递增也就是说相邻两个格子的数值必须一个比一个大相等都不行。从任何格子出发都可以路径长度按格子数量计算单个格子也算长度为 1 的路径。举个例子矩阵[[9,9,4],[6,6,8],[2,1,1]]最长递增路径是1 - 2 - 6 - 9长度是 4。很多人第一眼会以为答案跟“从最大值倒推”有关或者跟“每一行的最长连续递增子段”有关其实都不对因为路径在矩阵里可以随意拐弯绕开不合适的格子不受行、列的线性限制。这一点也是面试官最爱挖坑的地方他会在你讲思路时故意问一句“那从最大值出发开始搜行不行”如果你说不清楚为什么不行这道题基本就凉了一半。这个题的本质是把每个格子当成图里的一个节点如果相邻两个格子的值满足严格递增就连接一条从较小值指向较大值的有向边。因为数值严格递增边永远从小的指向大的图中不可能出现环所以整张图是一个有向无环图也就是 DAG。题目要求的“最长递增路径”本质就是这张 DAG 上的最长路。想明白这一点后面很多解法选择就顺理成章了。1.2 为什么第一反应DFS会超时直觉最简单的做法是对每个格子做一次 DFS枚举从它出发的所有递增路径最后取全局最大值。问题在于路径数量在最坏情况下是指数级的。比如一个按蛇形递增的矩阵每个格子的可选方向常常是两个以上路径分叉之后还会再次分叉O(2^(m×n))级别的枚举矩阵稍微大一点就 TLE。LeetCode 的约束是m, n 200暴力 DFS 在这种规模下根本没有生存空间。更隐蔽的问题是重复计算。从(0,0)出发的路径和从(0,1)出发的路径很可能在某个格子汇合汇合之后的那段子路径被反复枚举了无数次。这种“重叠子问题”正是动态规划和记忆化搜索要解决的典型信号。换句话说不是 DFS 这个思路错了而是少了“记忆”这一步。很多人在面试里栽跟头不是不会写 DFS而是没意识到暴力枚举背后那棵巨大的递归树其实是能被剪掉的。1.3 这题的真正身份DAG上的最长路既然矩阵能抽象成 DAG这题就有了不止一种解法。最贴近直觉的是 DFS 加记忆化搜索想展示功底可以用拓扑排序求最长路也可以把格子按值从小到大排序后做 DP。不同方法复杂度都在O(m×n)级别面试时选哪种直接决定了你是十分钟写完还是半小时改不完。我的建议是优先掌握 DFS记忆化。理由有三个第一不需要额外建图省掉很多结构代码第二代码量最少出错概率低第三它能体现“递归缓存”的通用思考模式换个题也能用。拓扑排序和排序 DP 作为进阶了解就行后面我会分别讲。实际刷题你会发现掌握好这一种解法LeetCode 上的一大批矩阵 DFS 问题都能顺手解决。2. 解法选型为什么会选DFS记忆化2.1 从暴力DFS到记忆化搜索的思考链从暴力 DFS 到记忆化搜索中间只差一个问题某个格子作为起点或者途经点时它到终点的最长路径会不会被多次询问答案是会。比如(0,0)的 DFS 会走到(0,1)(1,0)的 DFS 也可能走到(0,1)。只要(0,1)的结果被算过一次并缓存下来第二次遇到时直接取缓存不用重新枚举整棵子树。这个过程有点像登山的时候大家都会路过同一个观景台第一个人把路探明白了后面的人直接看路牌就行。这就是记忆化搜索的核心逻辑用memo[i][j]记录“从matrix[i][j]出发能形成的最长递增路径长度”。初始值设为 0表示还没计算过。每次进入递归先查缓存有就直接返回没有就去四个方向递归最后把结果写回缓存。这个“先查、再算、后写”的三步流程是所有记忆化搜索的标准套路。有人会问这个 DP 为什么不依赖遍历顺序因为递归是先处理“下游”也就是值更大的邻居而下游的结果天然与当前格子的计算无关所以不存在传统迭代 DP 里要先排序、先确定计算顺序的麻烦。这是 DFS记忆化和迭代 DP 最大的感知差异你不用管顺序递归的调用栈帮你把依赖关系理清楚了。已经习惯写传统 DP 的同学第一次接触这个特征时可能会有点别扭但多写几题就顺手了。2.2 状态定义与转移方程定义f[i][j]为从(i,j)出发的最长递增路径长度转移方程f[i][j] 1 max(f[ni][nj])其中(ni,nj)是(i,j)上下左右四个邻居里满足matrix[ni][nj] matrix[i][j]的那些格子。如果四个邻居都不满足那么 max 部分取 0f[i][j] 1表示路径只有当前这一个格子。这个方程是整道题的核心也是记忆化搜索的递归体。把它转成伪代码dfs(i, j): if memo[i][j] ! 0: return memo[i][j] best 1 for each valid neighbor (ni, nj) with matrix[ni][nj] matrix[i][j]: best max(best, 1 dfs(ni, nj)) memo[i][j] best return best这里的1代表从(i,j)走到邻居消耗的一步路径长度。选memo的类型时要注意这里必须用int而不是bool因为你要存的是“路径长度”这个数值不是一个简单的访问标记。用bool的后果是你得单独再开一个长度数组代码直接翻一倍。2.3 拿样例跑一遍递归过程以[[9,9,4],[6,6,8],[2,1,1]]为例。假设先调用dfs(0,0)也就是matrix[0][0]9。它的四个邻居分别是 9、6、越界、越界严格大于 9 的没有所以best保持 1memo[0][0]1直接返回。再看dfs(0,2)matrix[0][2]4它唯一有效的邻居是matrix[1][2]8于是进入dfs(1,2)。8的邻居里matrix[0][2]4小于它matrix[2][2]1小于它所以memo[1][2]1返回后memo[0][2]2。真正的长链在左下角matrix[2][1]1它下面越界左边matrix[2][0]2更大所以dfs(2,1)会触发dfs(2,0)matrix[2][0]2的右边matrix[2][1]1更小上面matrix[1][0]6更大于是进入dfs(1,0)6的上面matrix[0][0]9更大进入dfs(0,0)得到 1逐层返回后memo[1][0]2、memo[2][0]3、memo[2][1]4。全局最大值就是 4。这个链路里dfs(0,0)被多次引用但只有第一次真正递归后面全部命中缓存这就是记忆化的价值所在。2.4 复杂度分析为什么是O(m×n)每个格子的 DFS 只会真正计算一次之后所有调用都直接返回memo。每个格子计算时检查 4 个方向每次检查是常数时间所以总时间复杂度是O(m×n)。空间上memo是O(m×n)递归栈在最坏情况下深度可能接近m×n比如整个矩阵蛇形递增路径贯穿所有格子所以总空间复杂度也是O(m×n)。这个复杂度在 LeetCode 329 的约束下非常轻松。m, n 200意味着最多 4 万个格子每个格子常数时间计算运行时间通常在几毫秒到几十毫秒之间。很多人问“为什么我加了记忆化还是慢”排查下来基本都是缓存写错位置或者初始化错误导致记忆化根本没生效。为了更直观地对比我把三种常见解法的关键指标列在下面面试跟人讨论时可以直接引用这张表解法时间复杂度空间复杂度是否需要建图代码量DFS 记忆化O(m×n)O(m×n)否最少拓扑排序O(m×n)O(m×n)是中等按值排序 DPO(mn log mn)O(m×n)否中等3. 完整C实现与关键点拆解3.1 可以直接跑的完整代码#include vector #include algorithm using namespace std; class Solution { public: int m, n; int dir[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vectorvectorint memo; int longestIncreasingPath(vectorvectorint matrix) { m matrix.size(); if (m 0) return 0; n matrix[0].size(); memo.assign(m, vectorint(n, 0)); int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { ans max(ans, dfs(matrix, i, j)); } } return ans; } int dfs(const vectorvectorint matrix, int i, int j) { if (memo[i][j] ! 0) return memo[i][j]; int best 1; for (int k 0; k 4; k) { int ni i dir[k][0]; int nj j dir[k][1]; if (ni 0 ni m nj 0 nj n matrix[ni][nj] matrix[i][j]) { best max(best, 1 dfs(matrix, ni, nj)); } } memo[i][j] best; return best; } };我用类成员变量memo跨递归传递缓存m、n也存成成员变量这样dfs的签名可以短一点。如果你不喜欢成员变量也可以把memo作为引用参数传给dfs但在 LeetCode 的模板里成员变量的写法是最清爽的。另外dir我定义成int dir[4][2]而不是vectorpairint,int因为 C 风格数组在这里访问速度最快、写法最直观完全够用。3.2 逐段拆解关键代码入口函数先处理空矩阵if (m 0) return 0。这一步是防御性检查虽然 LeetCode 的单测数据一般不包含空矩阵但你在本地测试或者参加笔试时不要赌测试用例的良心。n matrix[0].size()必须在m 0之后否则空矩阵会访问matrix[0]直接越界。这种“先判空再取尺寸”的顺序是 C 刷题里最容易被忽略的崩溃点。memo.assign(m, vectorint(n, 0))把memo重置为全 0。这里用assign而不是clear再逐个填充省代码也省时间。之后两层循环遍历所有格子对每个格子调用dfs更新答案。注意这里必须遍历所有格子不要想当然只从最小值出发因为最长路径的起点不一定是全局最小值的格子。最典型的反例是[[1,2,3],[1,1,1]]全局最小值有两个但从左下角出发的路径只有 1真正的长链在上行。dfs里的比较条件是matrix[ni][nj] matrix[i][j]是严格大于不是大于等于。这个“严格”两字是很多人的失分点如果写成相等值的格子之间也能走了整个图就不是 DAG最坏情况下会死循环或者直接 WA。我见过不止一个人栽在这个小地方自查的时候第一眼先看这里。3.3 为什么返回值可以直接累加1 dfs(ni, nj)里的1表示“从(i,j)走到(ni,nj)”这个动作增加的一步路径。dfs(ni,nj)返回从邻居出发的最长路径长度两者相加就是“从(i,j)出发、第一步走(ni,nj)”的候选路径长度。对所有候选方向取max再和兜底值 1 比较就能得到(i,j)的最优解。这个设计逻辑上是严密的每个状态只依赖值更大的邻居严格递增保证递归不会出现循环依赖所以一定会终止。memo[i][j] best放在递归返回之前确保每个格子只算一次。这里有个隐藏的战术点第一次进入dfs(i,j)时best先设为 1而不是 0。如果设成 0那么没有更大邻居的格子会返回 0整条链路都会少 1答案全错。这个错非常隐蔽因为小矩阵上可能刚好被其他分支掩盖大矩阵上就会差之毫厘谬以千里。3.4 边界条件别偷懒DFS 内部的越界检查ni 0 ni m nj 0 nj n必须写在访问matrix[ni][nj]之前。逻辑顺序错了会导致越界访问C 里这种错误有时候不会立刻崩溃而是读出脏数据表现成莫名其妙的 WA。排查非常痛苦所以我的习惯是所有 DFS 类题目越界判断永远在数组访问之前一行都不能省。另一个细节是const vectorvectorint matrixconst和引用缺一不可。传值会导致每次递归都深拷贝整个矩阵复杂度直接多乘一个m×n大数据下就是 MLE 或 TLE。在 C 里写 LeetCodevectorvectorint的传递方式是一个高频考点很多人代码逻辑全对就挂在传值上。还有一个小点是matrix[0].size()之后最好确认一下matrix[0]非空虽然 LeetCode 不给[[]]这种极端输入但自己写测试时可能会遇到。4. 实测中踩过的坑与排查技巧4.1 递归栈溢出问题理论上递归栈最大深度是m×n也就是 4 万层。C 默认的栈空间在多数评测环境里够用但如果你把代码搬到某些限制严格的平台或者把矩阵改成更大规模做压力测试可能会爆栈。LeetCode 329 用递归写没有任何问题但心里要有这根弦。万一真的爆栈有两个方向一是把 DFS 改成显式栈的迭代写法二是用下一节讲的拓扑排序。我在本地做压力测试时确实遇到过一次爆栈原因是编译器栈大小被限制得很小改成迭代后问题消失。不过对绝大多数面试场景递归写法就够了不需要过度设计。在面试里与其花二十分钟改成迭代不如主动跟面试官说清楚递归深度的量级和风险他反而觉得你考虑周全。4.2 记忆化没生效的典型表现代码写完发现运行时间跟暴力 DFS 差不多或者大数据集还是 TLE基本可以断定记忆化没生效。常见原因有三个第一memo赋值位置写错比如在递归体里先写memo[i][j]best但best还没计算完导致缓存全是错误值第二memo定义成递归函数的局部变量每次调用都重新创建缓存形同虚设第三把memo和visited搞混递归返回后又清零。排查方法很简单加一个计数器统计dfs真正进入循环体的次数。如果次数接近m×n而不是远大于此说明缓存正常工作。如果次数远超m×n那就检查上面的三个原因。这个方法对绝大多数记忆化题目都通用建议记下来。我每次新写一个记忆化 DFS都会习惯性先打这个计数器跑一遍小样例验证确认缓存生效了再继续下一步。4.3 从TLE到AC的调试顺序如果代码 TLE我建议按这个顺序排查。第一步确认有没有记忆化没有就直接补上。第二步确认记忆化被正确写入和复用重点检查memo是成员变量而不是递归内新建。第三步看方向是否写错导致反复回溯或重复遍历。第四步确认matrix是引用传递。按这个顺序走一遍绝大多数性能问题都能定位。不要一上来就怀疑算法选型先检查最基础的“记忆化是否生效”90% 的 TLE 出在这个地方。如果确认是算法本身的问题比如矩阵规模真的特别大那再考虑拓扑排序或者把递归改成迭代。但在 LeetCode 的原始约束下DFS记忆化就是最优解之一不需要额外优化。还有个小技巧把dir数组和memo都设计成成员变量可以避免递归函数参数过长也能让编译器更好地优化访问。4.4 建议自测的经典用例刷完题一定要跑这几个用例我每次做矩阵类 DFS 都会准备一份本地测试用例预期结果说明[[1]]1单格子兜底[[1,2],[2,1]]2双向都不能成环[[1,2,3],[6,5,4]]6蛇形长链贯穿全矩阵[[7,7,7],[7,7,7],[7,7,7]]1全相等时严格递增失效[[9,9,4],[6,6,8],[2,1,1]]4官方样例最后一个全相等用例特别容易错如果比较条件误写成答案会变成 9。把这些用例写进本地自动化测试每次改代码随手跑一遍能挡掉很多低级错误。我自己在写题解的时候甚至会把这些用例并排放在一个测试函数里改一行代码跑一次全量虽然多花几秒钟但心里踏实。5. 进阶这题还能怎么考5.1 拓扑排序求最长路既然矩阵是 DAG用拓扑排序也能算最长路。先对每个格子建图从当前格子指向值更大的邻居。统计每个节点的入度把入度为 0 的节点入队。按拓扑序逐层推进维护每个节点到起点的最长距离最后取全局最大值。这种做法的本质是对 DAG 做一次层级遍历每处理一层就把下一层的候选距离更新一轮。这个写法的好处是不用递归也不担心栈深度但代码量会多不少。我推荐至少写一遍因为面试官很吃“我能从图论角度理解这个题”这套说辞。写的时候注意入度是“有多少个值更小的邻居连向当前格子”建表时就要确定方向别把出度和入度搞反。真搞反了也不会马上报错只是答案会变成 1非常迷惑人。5.2 按值排序的DP写法另一个思路是把所有格子按值从小到大排序然后从小到大处理。对当前格子找它四个方向里值更小且已经处理过的邻居用dp[cur] max(dp[cur], 1 dp[neighbor])更新。因为值是递增处理的处理到当前格子时所有更小邻居的dp都已算好天然满足 DP 的顺序要求。这个写法排序要先花O(mn log mn)总体比 DFS记忆化的O(mn)多一个 log 因子。数据量小的时候测不出来但作为一个“第二种解”写在笔记里是加分的。不少经典题解把这种写法称为“真正意义上的动态规划”把记忆化搜索称为“带缓存的 DFS”两边都掌握面试时就能随意切换。实际使用时要注意排序的稳定性如果两个格子值相等它们之间是不能连边的所以相等值的格子谁先处理都无所谓。5.3 相关变形题LeetCode 329 的变形题不少。把“递增”改成“严格递减”不用改算法把比较方向反过来或者把矩阵每个值取相反数再跑一遍即可。要求从指定起点出发的版本先跑一次全矩阵 DFS再查指定格子的memo值复杂度不变。要求输出最长路径格子序列的版本则需要额外维护一个next数组在best更新时记录后继方向最后回溯构造路径。这些变种万变不离其宗核心都是“用记忆化消除重叠子问题”。还有一类更隐蔽的变形是把二维矩阵压成一维数组或者把移动方向从 4 个变成 8 个比如加入斜向移动。这时候只要把方向数组改一下其余逻辑几乎不用变。学会这个题之后你会发现矩阵上的很多路径问题都能套用同一套“DFS记忆化”模板区别只是状态定义和转移条件不同。最后说点个人体会。我在面试里遇到过一次这道题当时第一版写的暴力 DFS小样例能过面试官让我分析复杂度我算出来指数级自己都不好意思。改成记忆化之后代码反而更短思路也清晰很多。那次之后我养成一个习惯凡是“矩阵路径”的题先问自己路径会不会有环一旦确认无环就优先往 DFS记忆化或拓扑排序想。最后分享一个小技巧面试时即使你写 DFS记忆化也主动说一句“这本质是 DAG 最长路”比闷头背代码有用得多。

LeetCode 329 最长递增路径：C++ DFS+记忆化搜索详解

相关推荐

自愿的负载：Ω–L叠层体系的生命定义

Claude Code模板化实战：从CLAUDE.md到子代理的完整指南

Docker部署wechat-article-exporter：公众号文章批量下载与归档实战

更多资讯

2026年自动化测试趋势：无代码革命与脚本下沉

测试转开发实战指南：技能迁移路径与多方向技术选型

图书数据分析可视化系统：从爬虫到推荐的Django全栈实践

Unity GC卡顿排查与优化：从原理到实战的帧率保卫指南

冀州全屋定制源头加工厂哪家口碑好、全屋定制源头供应企业哪家专业、全屋定制源头制造企业哪家靠谱用户力荐

Linux基础知识点梳理：文件权限、常用命令与系统运维实战

今日更新

BunnyScholar硕士论文跨章节检查：长文档双栏如何梳理因果链

维普标红教育学SEM量表怎么办：助研君修改与RMSEA指标复核

知网标红有限元仿真与网格划分怎么办：助研君按字修改与参数复核

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？