LeetCode 329. 矩阵中的最长递增路径
题目描述
题意分析
可以从矩阵中的任意格子出发，每一步只向上、下、左、右移动，并且下一个格子的值必须严格大于当前值。返回所有合法路径中最大的格子数量，不要求返回路径本身。
相等值不能相连，也不能沿对角线或跨越边界移动。不同起点可能汇入同一个格子，共享后面的递增路径；如果每次都重新向后搜索，会反复计算同一部分，因此需要保存每个格子的最优结果。
解法：DFS 记忆化搜索
核心思路
[!blue]
定义
memo[row][col]为从当前格子出发能得到的最长递增路径长度。它只描述从这里往后走的部分，不包含到达这里之前经过多少格，因此无论哪个起点搜索到这里，都可以复用同一个结果。这种复用为什么不需要知道来路？已经走过的格子都比当前值小，后面又只能走向更大的值，不可能回到之前的路径上。严格递增也排除了任何环，因此无需额外记录当前路径的访问集合。
一条从当前格子出发的路径，要么停在当前格子，长度为
1；要么走向某个更大的相邻格，再接上从那个邻居出发的最优路径。因此先令best = 1，枚举全部合法且更大的邻居，用dfs(邻居) + 1取最大值。不能遇到第一个可走方向就返回，因为不同方向的后续长度可能不同。
memo初始为0，而任何实际路径长度至少是1，所以0可以明确表示尚未计算。DFS 命中非零缓存时直接返回，否则先完成所有邻居的比较，再把最终值存入缓存。没有更大邻居时保留1，自然处理局部最大值和单个格子。最后枚举每个格子作为起点，对返回值取最大值。最长路径可能位于矩阵任何位置，不能只从左上角或全局最小值出发。记忆化使各个起点共享已算好的后缀，每个格子的状态只真正计算一次。
解题步骤
- 创建与矩阵同尺寸、初始全为
0的memo，初始化全局答案。- 枚举每个格子作为起点，调用 DFS 并更新全局最大长度。
- DFS 若已有缓存，直接返回；否则令本格最优长度
best = 1。- 检查四个方向，只递归访问未越界且值严格更大的邻居，用返回长度加一更新
best。- 比较完全部方向后写入
memo[row][col]，再返回这个结果。
代码实现
class Solution {
private static final int[][] DIRS = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
};
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] memo = new int[m][n];
int ans = 0;
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
ans = Math.max(ans, dfs(matrix, memo, row, col));
}
}
return ans;
}
private int dfs(int[][] matrix, int[][] memo, int row, int col) {
// 缓存的是从此格出发的最长路径，其他起点可直接复用。
if (memo[row][col] != 0) {
return memo[row][col];
}
int best = 1;
for (int[] dir : DIRS) {
int nextRow = row + dir[0];
int nextCol = col + dir[1];
if (nextRow >= 0
&& nextRow < matrix.length
&& nextCol >= 0
&& nextCol < matrix[0].length
&& matrix[nextRow][nextCol] > matrix[row][col]) {
best = Math.max(best, dfs(matrix, memo, nextRow, nextCol) + 1);
}
}
// 只有更大邻居才能延伸，不会成环；全部候选比较后保存结果。
memo[row][col] = best;
return best;
}
}
var directions = [4][2]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
memo := make([][]int, m)
for row := range memo {
memo[row] = make([]int, n)
}
ans := 0
for row := 0; row < m; row++ {
for col := 0; col < n; col++ {
length := dfsIncreasing(matrix, memo, row, col)
if length > ans {
ans = length
}
}
}
return ans
}
func dfsIncreasing(matrix, memo [][]int, row, col int) int {
// 缓存的是从此格出发的最长路径，其他起点可直接复用。
if memo[row][col] != 0 {
return memo[row][col]
}
best := 1
for _, direction := range directions {
nextRow := row + direction[0]
nextCol := col + direction[1]
if nextRow >= 0 && nextRow < len(matrix) &&
nextCol >= 0 && nextCol < len(matrix[0]) &&
matrix[nextRow][nextCol] > matrix[row][col] {
candidate := dfsIncreasing(matrix, memo, nextRow, nextCol) + 1
if candidate > best {
best = candidate
}
}
}
// 只有更大邻居才能延伸，不会成环；全部候选比较后保存结果。
memo[row][col] = best
return best
}
复杂度分析
- 时间复杂度：$O(mn)$。每个格子的状态只计算一次，每次固定检查四个方向。
- 空间复杂度：$O(mn)$。
memo占 $O(mn)$，递归栈最坏也可能达到 $O(mn)$。
关键点总结
[!green]
- 严格递增使图天然无环，因此无需
visited。- 状态必须定义为“从当前格子出发”的最长长度，才能跨起点复用。
- 单格路径长度为 1，所以
best初始化为 1，0 可作为缓存哨兵。- 当前枚举所有格子作为起点，借助缓存共享后续路径，无需提前猜测哪个起点最优。
易错点总结
[!yellow]
- 允许相等值继续移动：会违反严格递增要求，并可能在相等邻居之间反复递归。
- 把来路长度纳入缓存：同一个格子可能由不同长度的前缀到达，只有从此格出发的后缀长度才能共享。
- 遇到缓存只跳过而不取回长度：父状态仍需要这个格子的最优后缀，应返回缓存结果。
best初始化为0：当前格子本身也计入路径，至少应为1。- 只尝试一个起点或一个邻居：最长路径可能从任意位置出发，也可能走向任何一个更大的邻居，必须比较完整候选范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 同样利用严格递增关系，本题相邻条件来自网格，每格最优长度需记忆化。 |
| 207. 课程表 | 中等 | 按数值严格递增方向连边后天然无环，可从有向无环图的拓扑层次理解最长路径。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！