矩阵最长路径算法详解：从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 在思路上一模一样，代码会更紧凑。笔试环境一般支持 C++11 及以上，我习惯用全局数组，并加上输入输出优化。

#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 里跑一遍，确认三种实现输出一致。我常用的验证用例有这些：

拿“路径会拐弯”那个用例手推一下：

矩阵： 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 能走到 B，B 也能走到 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，强烈建议你也试试。

这道题后续还能继续扩展成“矩阵最长下降路径”或者“带权值的最大爬楼得分”，但万变不离其宗。把状态定义、记忆化含义、比较符号三个点抓牢，换什么壳都不怕。