矩阵最长路径算法详解：从DFS到记忆化搜索的笔试实战-北京尧图网络

最近刷春招真题的时候碰到一道很典型的算法岗笔试题题面披着“爬山”的外衣骨子里却是经典的矩阵最长路径问题。某电商平台把它放在算法岗笔试第三题的位置说明出题人对候选人DFS和动态规划基本功的看重。这篇文章就把题目、解题思路、三种主流语言的AC代码以及我在本地反复测试时踩过的坑全部整理出来。这道题本身没有任何冷门算法一个合格的计算机专业学生都应该能想到深度优先搜索。但笔试不是“想到思路就给分”它考察的是你在有限时间内能不能把思路落地成一份稳定、高效的代码。我见过不少同学能口述记忆化搜索的思路一到手写就卡在方向数组、边界检查、递归初始化这些细节上非常可惜。这篇文章会把这些都补全。1. 题目还原与考点拆解1.1 题面怎么说整理后的题目描述如下给定一个 m 行 n 列的矩阵每个格子里的正整数代表该位置的海拔。你可以从任意一个格子出发每一步只能走到上下左右四个相邻方向中的一个格子且要求下一格的海拔严格高于当前格子。求在整个矩阵中按照这个规则能走出的最长路径包含多少个格子。输入格式一般是第一行两个整数 m、n表示矩阵的行数和列数接下来 m 行每行 n 个正整数表示每个点的海拔。输出一行一个整数表示最长路径的格子数。题目有几个关键约束需要盯住起点不固定矩阵里任意一格都能当起点只能上下左右移动不能斜着走下一格海拔必须严格大于当前格相等高度不能转移输出的是“格子数”不是“边数”。比如走了 5 步经过的格子数是 6笔试里这两个表述混用很容易丢分。我习惯先读一遍题然后直接把“严格大于”四个字圈出来。这四个字决定了图的方向性和无环性是整个算法成立的前提。1.2 这题到底在考什么把“爬山”这个壳拆掉之后问题本质是在一个有向无环图上求最长路径。矩阵里每个格子是一个节点如果格子 A 能一步走到格子 B就存在一条从 A 指向 B 的有向边。因为要求海拔严格递增所以不可能存在环——你不可能从低处爬到高处之后再绕回这个低处。这是所有解法的合法性基础。最经典的解法是 DFS 加记忆化搜索也有人叫它“带备忘录的深度优先搜索”。具体来说我们定义一个状态 dp[i][j] 表示从格子 (i, j) 出发能走出的最长路径长度。这个状态可以递归求解dp[i][j] max(dp[i][j], 1 dp[相邻格])前提是相邻格的海拔大于当前格。如果四个方向都没有更高的格子dp[i][j] 就是 1表示只能停在原地。在各类在线题库里这道题的原型叫“矩阵最长递增路径”是一道很经典的图论和动态规划综合题。笔试只是把方向包装成了“爬山”有的题目版本会反过来要求“下山”也就是走到高度严格小于当前格子的位置那代码里只需要把大于号改成小于号即可其余完全一致。1.3 和大厂高频题的对应关系这道题在春招算法岗笔试里出现频率很高因为它能在一个小题里同时考察好几个基本功深度优先搜索的递归写法记忆化剪枝也就是用空间换时间方向数组的书写和坐标合法性校验对图论中“无环”本质的敏感度。很多大厂校招笔试题喜欢把经典题换个业务场景的外壳出出来比如把矩阵换成地图、把海拔换成积分数、把路径换成任务链。如果你只背题不练原理换壳之后很容易慌乱。相反如果真正理解了“有向无环图最长路径”的模型不管它包装成爬山、滑雪还是闯关你都能在一分钟内把壳拆掉。2. 核心思路拆解从暴力DFS到记忆化搜索2.1 裸DFS为什么必挂很多人的第一反应是从每个点开始 DFS搜出从该点出发的最长路径然后取最大值。这个思路方向没错但是完全没有加记忆化的裸 DFS 在笔试环境下必超时。原因很简单同一个格子会被重复计算很多次。举个例子一个 3×3 的矩阵里如果数字排成一个螺旋阶梯从左上角出发的路径可能有几十条每条路径都会重复访问中间的格子。而矩阵最大可以到 200×200最坏情况下朴素 DFS 的搜索次数是指数级的4 个方向反复试探没有剪枝的话根本跑不完。用生活里的感觉类比一下你从山顶沿着溪流往下走走了很久到了半山腰又发现另一条路绕回了这个半山腰。正常人的做法是记住“从这个半山腰往下最长能走多远”下次再路过直接查本子而不是重新把半山腰以下的每条路再走一遍。记忆化搜索干的就是这件事。裸 DFS 的时间复杂度难以用简单公式表达但最坏情况下会随着路径长度呈指数爆炸。笔试数据只要稍微大一点TLE 是必然的。2.2 记忆化搜索是怎么省时间的记忆化搜索的核心思想是每个格子的 dp 值只计算一次之后再次用到时直接返回。我们用 memo[i][j] 记录从 (i, j) 出发的最长路径长度。第一次 dfs 到某个格子时递归计算它的四个方向得到结果后存入 memo后面任何路径再走到这个格子直接从 memo 里取值不再递归展开。因为矩阵里每个格子作为递归的“入口”只会被完整执行一次所以总时间复杂度是 O(m×n)。每个节点在计算时要检查四个邻居因此准确说复杂度是 O(4×m×n)也就是 O(m×n)。空间复杂度同样为 O(m×n)用来存 memo 数组。这个优化看起来平淡无奇却是从指数级到多项式级的质变。200×200 的数据规模对裸 DFS 可能是天文数字对记忆化搜索也就是 4 万多次状态计算眨眼之间。2.3 状态转移方程和复杂度用数学形式写一下设 dfs(i, j) 返回从 (i, j) 出发的最长路径长度。题目要求下一步只能走到海拔更高的位置所以dfs(i, j) 1 max(dfs(x, y))其中 (x, y) 是 (i, j) 四个方向上的相邻格子且满足 height[x][y] height[i][j]。如果没有满足条件的相邻格子则 dfs(i, j) 1。最终的答案等于所有格子出发值的最大值ans max(dfs(i, j))对矩阵中所有 (i, j) 取最大。这里有一个很容易被忽略的数学前提因为高度严格递增所以整个状态依赖关系是一个偏序不存在循环依赖。这意味着记忆化搜索不会出现“ A 依赖 B、B 又依赖 A ”的死锁情况。这也是面试时考官最想听到的“为什么会话”的解释。如果你能把“无环所以可以记忆化”这句话说清楚就已经抓住这道题的精髓了。3. 三种语言的满分写法3.1 Java怎么组织全局变量Java 写这道题的时候最常见的问题是全局变量和局部变量分不清。笔试平台通常要求提交一个包含 main 方法的类我会把矩阵、memo、方向数组都定义成静态成员变量这样 DFS 方法里不需要反复传参代码更干净。import java.util.Scanner; public class Main { static int[][] height; static int[][] memo; static int m, n; static int[] dx {-1, 1, 0, 0}; static int[] dy {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc new Scanner(System.in); m sc.nextInt(); n sc.nextInt(); height new int[m][n]; memo new int[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { height[i][j] sc.nextInt(); } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { ans Math.max(ans, dfs(i, j)); } } System.out.println(ans); } static int dfs(int i, int j) { if (memo[i][j] ! 0) { return memo[i][j]; } int best 1; for (int k 0; k 4; k) { int x i dx[k]; int y j dy[k]; if (x 0 x m y 0 y n height[x][y] height[i][j]) { best Math.max(best, 1 dfs(x, y)); } } memo[i][j] best; return best; } }几个 Java 版本的注意点memo 数组默认值是 0而每一条合法路径最少也包含当前格子本身也就是长度至少为 1所以用 0 表示“还没算过”是安全的四个方向的定义顺序无所谓但一定要保证 dx 和 dy 下标对齐判断相邻格子合法时x 和 y 的边界检查必须写在数组访问之前否则会出现数组越界异常。另外Scanner 在笔试数据规模下没有问题不必刻意优化输入。如果你实在担心 200×200 的数据量可以换成 BufferedReader 包装一下但收益很小不值得为此增加代码复杂度。3.2 C数组和输入输出优化C 版本和 Java 在思路上一模一样代码会更紧凑。笔试环境一般支持 C11 及以上我习惯用全局数组并加上输入输出优化。#include bits/stdc.h using namespace std; const int MAXN 205; int height[MAXN][MAXN]; int memo[MAXN][MAXN]; int m, n; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int dfs(int i, int j) { if (memo[i][j] ! 0) { return memo[i][j]; } int best 1; for (int k 0; k 4; k) { int x i dx[k]; int y j dy[k]; if (x 0 x m y 0 y n height[x][y] height[i][j]) { best max(best, 1 dfs(x, y)); } } memo[i][j] best; return best; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin m n; for (int i 0; i m; i) { for (int j 0; j n; j) { cin height[i][j]; } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { ans max(ans, dfs(i, j)); } } cout ans \n; return 0; }为什么 C 版本要写ios::sync_with_stdio(false)因为默认情况下 C 的 cin 和 C 的 stdio 是同步的会有额外开销。笔试里数据量不大这个优化不明显但养成习惯没坏处。C 全局数组默认清零memo 初始就是 0所以不需要额外初始化。数组大小开 205 是因为题目写了 m、n 最大 200留一点余量。如果题目边界改到 500记得同步调整 MAXN。和 Java 相比C 的代码在内存布局上更紧凑运行速度也要快一些。但笔试阅卷不比较常数重点是逻辑正确。3.3 Python递归深度问题与三种解法Python 解法最核心的问题是递归深度。C 和 Java 的递归可以很深Python 默认递归层数限制是 1000如果矩阵恰好是一条从低到高的超长阶梯路径长度可能超过 1000 层直接报 RecursionError。我给出三种处理方式笔试现场可以根据具体情况选用。第一种手动调大递归限制配合记忆化数组。import sys sys.setrecursionlimit(1 20) def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) m int(next(it)) n int(next(it)) grid [[int(next(it)) for _ in range(n)] for _ in range(m)] memo [[0] * n for _ in range(m)] dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j): if memo[i][j]: return memo[i][j] best 1 for di, dj in dirs: x, y i di, j dj if 0 x m and 0 y n and grid[x][y] grid[i][j]: best max(best, 1 dfs(x, y)) memo[i][j] best return best ans 0 for i in range(m): for j in range(n): ans max(ans, dfs(i, j)) print(ans) if __name__ __main__: solve()第二种用 functools 的 lru_cache 装饰器代替手写 memo。from functools import lru_cache lru_cache(None) def dfs(i, j): best 1 for di, dj in dirs: x, y i di, j dj if 0 x m and 0 y n and grid[x][y] grid[i][j]: best max(best, 1 dfs(x, y)) return best注意 lru_cache 虽然自动缓存结果但递归深度问题依然存在需要配合 setrecursionlimit 使用。它内部是用字典存状态200×200 的规模没有问题。第三种完全不用递归按高度排序后递推。把每个格子按照高度从小到大排序状态 dp[i][j] 等于“周围所有高度更低的格子状态 1”的最大值。因为矮格子先算高格子后算后算的格子一定能用到已经算好的矮格子结果。这个思路可以写成cells [(grid[i][j], i, j) for i in range(m) for j in range(n)] cells.sort() dp [[1] * n for _ in range(m)] for h, i, j in cells: for di, dj in dirs: x, y i di, j dj if 0 x m and 0 y n and grid[x][y] h: dp[i][j] max(dp[i][j], dp[x][y] 1) ans max(max(row) for row in dp)这种方式彻底避开递归可以处理更大的矩阵代价是排序需要 O(m×n×log(m×n)) 的时间。笔试中 200×200 的数据规模下完全够用。如果你在面试环节被问“能不能不用递归实现”这个递推方法是一个很好的加分回答。4. 在线测试与边界用例4.1 手算用例对照表看完代码之后我建议你不要直接提交先自己构造几个小用例在本地或者在线 IDE 里跑一遍确认三种实现输出一致。我常用的验证用例有这些用例输入期望输出说明基础3 3 / 4 3 1 / 2 5 6 / 8 9 75路径会拐弯不是一条直线全相等2 2 / 5 5 / 5 51严格大于不成立任何格子都只能停在原地单行1 4 / 1 2 3 44直线递增一直走到头单列3 1 / 7 / 8 / 93竖向爬升单格1 1 / 421最小规模高度倒序2 2 / 4 3 / 2 11处处下降无法向更高处走拿“路径会拐弯”那个用例手推一下矩阵 4 3 1 2 5 6 8 9 7从数字 1 出发第一行第三列可以走 1 - 3 - 4长度 3也可以走 1 - 6 - 9长度 4还可以走 1 - 6 - 9 后停住。如果从 1 出发走 3 - 5 - 8 - 9因为 5 和 9 不直接相邻这个路径不成立。实际最长路径之一1 - 3 - 5 - 8 - 9或者 1 - 2 - 5 - 8 - 9长度 5。这种包含拐弯的用例最适合验证你自己的代码有没有把“上下左右”四个方向都枚举全。4.2 边界条件专项测试除了用例表边界条件我强烈建议单独写一组测试。最容易翻车的三个边界场景第一单行矩阵。此时上下两个方向越界代码必须能正常处理。如果你只测试了行列都大于 1 的情况单行输入很可能暴露出方向数组越界问题。第二全相同矩阵。严格递增条件下每个格子都无法向邻居移动答案应该是 1。如果你把写成在双相等格子的场景下A 能走到 BB 也能走到 A递归就会出现互相调用的死循环程序直接栈溢出。这是一个非常隐蔽的致命错误。第三最大规模随机大矩阵。构造一个 200×200 的全随机矩阵跑一遍看耗时。记忆化搜索应该在一秒内完成。如果超过 5 秒多半说明记忆化没有生效或者递归层数导致栈空间耗尽。4.3 在测评环境中的提交技巧笔试系统的输入输出格式一定要看清楚。这道题常见的输入是以空格或换行分隔数字我的代码用split()读取所有数字再迭代处理就是为了适应不同分隔方式。如果题面保证每个矩阵元素单独一行你也可以用input()逐行读取但统一用read()方式更稳健。提交时注意两点不要带包名类名必须是题面要求的一般就是Main输出结尾最好带换行符虽然很多系统不检查末尾换行但带上最安全。我在自测时有个习惯先把代码里的 main 方法里的数据改成硬编码的二维数组跑一遍确认答案正确再改回标准输入输出提交。这样能把“算法逻辑问题”和“IO 解析问题”分开排查。5. 笔试现场常见错误与排查5.1 严格递增写成非严格递增这是我见到的第一高频错误。题目说的是“严格高于”对应代码是不是。一旦用成两个等高的相邻格子就可以互相走动形成合法环。递归里出现环最终结果是栈溢出或者超时而且报错信息不会告诉你“这里有环”排查起来很痛苦。我也见过反向错误题目要求“严格大于”代码却写成导致的 RE。所以提交前我建议你刻意构造一组全部等高的输入跑一遍。如果输出不是 1那你的比较符号一定写错了。5.2 方向数组越界与坐标检查漏写方向数组是每次手写 DFS 最容易出错的地方之一。我习惯写成两组独立的数组int[] dx {-1, 1, 0, 0}; int[] dy {0, 0, -1, 1};这四个方向的顺序是上、下、左、右。无论顺序怎么换关键是访问height[x][y]之前必须确认 x 和 y 都在矩阵范围内。漏掉边界检查的典型结果有两种一是语言层面的数组越界异常Java 直接抛异常终止二是 C 里未定义行为本地可能偶尔能跑平台上报 WA 或 RE表现非常随机。我建议把边界检查封装成一行固定写法if (x 0 x m y 0 y n ...)不要写成四个 if 嵌套那样既慢又容易漏。5.3 递归爆栈与本地编译通过但平台报错这个问题在 Java 和 Python 上比较常见。虽然调大setrecursionlimit能解决 Python 的 RecursionError但如果你把 limit 调得过大比如 1 30在某些环境里可能引发段错误。比较稳妥的做法是配合第三种递推方案毕竟它完全不依赖递归。C 很少会因为 200×200 的矩阵爆栈但如果你把全局数组换成了局部大数组又恰好在 main 函数里可能因为栈空间不足导致崩溃。笔试中我不会用vector的局部二维大数组在 main 里开 200×200反而是全局数组最省心。还有一个很实际的排查技巧如果本地跑小数据正确、提交平台却 WA先不要怀疑算法重新读一遍题目检查是不是“输出格子数”而不是“输出边数”。这道题稍不留神就会输出 max(dp) - 1那就白丢分了。6. 这道题的扩展与备考建议6.1 变形题目这道题可以往很多方向变形下面几种是面试官最爱追加的如果允许斜对角移动方向数组要从 4 个变成 8 个复杂度不变如果要求输出最长路径本身需要额外维护一个前驱数组在更新 best 时记录来自哪个方向如果矩阵很大比如 1000×1000递归方案风险高推荐使用排序递推或拓扑排序如果改成“从任意点出发高度先升后降的最大子路径”就变成了两遍 DP 的组合问题。每种变体背后都是同一个核心把状态定义清楚然后保证无后效性。状态转移不存在环形依赖就可以用记忆化存在环形依赖就需要重新定义状态或者用更复杂的算法。6.2 记忆化搜索的通用模板我把这类题的“三板斧”总结成一个模板做熟了之后很多矩阵上的路径问题都可以套第一步定义 dfs(i, j) 表示从当前格子出发能获得的某种最优值第二步枚举方向数组对合法邻居递归调用第三步用 memo 数组记录已计算状态返回前存入第四步遍历所有起点取最大值。记住这个模板只需要五分钟但能救回笔试里的很多时间。笔试时遇到矩阵路径、棋盘移动、网格规划类题目先往这个模板上靠大概率方向不会偏。6.3 这类题怎么刷我个人的刷题建议是把它归入“网格图状态搜索”这一大类和岛屿数量、迷宫最短路径、骑士巡游这些题放在一起对比练习。重点不是背代码而是弄清楚每个题为什么能用记忆化、为什么不能用普通的动态规划递推。面试时如果被问到优化可以主动说三种思路记忆化搜索、按高度排序递推、拓扑排序剥洋葱。三种思路复杂度略有差异但都能 AC区别在于对数据规模的适应性。你只要能讲明白第一种再顺带提一句“极端数据下还可以排序递推”考官通常就比较满意了。我在实际笔试中还会多写一个快速自测函数把案例 3 3 / 4 3 1 / 2 5 6 / 8 9 7 写死在代码里跑一遍输出 5 才提交。这个习惯帮我拦截过好几次因为方向数组写错而导致的 WA强烈建议你也试试。这道题后续还能继续扩展成“矩阵最长下降路径”或者“带权值的最大爬楼得分”但万变不离其宗。把状态定义、记忆化含义、比较符号三个点抓牢换什么壳都不怕。

矩阵最长路径算法详解：从DFS到记忆化搜索的笔试实战

相关推荐

DeepSeek Harness：Agent插件化底座的核心设计与工程实践

每日编程英语打卡：三道算法题精讲与单词记忆法

Java学习第一天：搭建JDK环境、理解JVM与运行Hello World

更多资讯

Windows笔记本Pytorch CPU版安装指南：从零到跑通

双节锂电池主动均衡方案：MP2642GR-Z与PIC18LF47K40协同设计

Elasticsearch 指标聚合详解：cardinality、stats、percentiles 与 string_stats

MP2642GR-Z与ATmega6450协同实现高可靠电池均衡

Zabbix告警收不到？用Python脚本实现稳定SMTP邮件告警配置指南

A*寻路算法从原理到实战：启发函数、性能调优与避坑指南

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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