LeetCode 329困难二维动态规划
矩阵中的最长递增路径 图解题解
这道题到底在问什么
在矩阵中只能走到更大的相邻格，求最长递增路径长度。
- 示例
- [[9,9,4],[6,6,8],[2,1,1]] → 4
先想最直接的笨办法
从每个格子暴力 DFS 会重复计算后缀路径。（动画第 3 步）
最优解：一步一步想明白
- 3从每个格子暴力 DFS 会重复计算后缀路径。
- 4memo[r][c] 记从该格出发的最长递增路，四方向只走更大值。
- 5每个格子算「从我出发，沿严格递增能走多远」，结果存进 memo，重复用到时直接取，不再重算。
- 61(在 (2,1)) 的邻居里只有 2(在 (2,0)) 比它大 → 走过去，路径长度 2。
- 72 → 6（6＞2），路径长度 3，继续找更大的邻居。
- 86 → 9（9＞6），已沿 1→2→6→9 走了 4 步到顶。注意区分：memo 记的是「从该格往后」的最长——9 周围没有更大邻居，从 9 出发只有它自己，所以 memo[(0,0)]=1。
- 9回溯时层层 +1：memo[(0,0)]=1 → memo[(1,0)]=2 → memo[(2,0)]=3 → memo[(2,1)]=4。对所有格子取最大 → 最长递增路径 ＝ 4。
- 12另一个要点：判环？不用。路径只能严格递增，数值一路变大、绝不回头，所以天然无环，省掉 visited 数组。
- 15记忆化的威力：这条路径上 4 个格子的最长值都已存好。别的起点(如右下角 1→8)若经过它们，直接读 memo、不再重算 —— 这正是把指数级降到 O(m·n) 的关键。又因严格递增天然无环，全程不需要 visited。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“memo 为什么能让每格只算一次”。
⚠️ 容易写错的地方
✗ 错：裸 DFS 不加 memo
✓ 对：用 memo 缓存每格的最长路径
不同起点会反复重算公共子路径，最坏指数级；memo 让每格只算一次 O(m·n)。
✗ 错：为防环加 visited 标记
✓ 对：不需要 visited
只能走向「严格更大」的邻居，路径单调递增、不可能回到走过的格子，天然无环。
✗ 错：路径条件写成 ≥（含相等）
✓ 对：必须严格 ＞（递增）
相等会形成环、且不符合「严格递增」定义。
完整代码（Python / C++ / Java）
Python
class Solution:
def longestIncreasingPath(self, matrix):
rows, cols = len(matrix), len(matrix[0])
memo = {}
def dfs(r, c):
if (r, c) in memo:
return memo[(r, c)]
best = 1
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[(r, c)] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))C++
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m=matrix.size(), n=matrix[0].size();
vector<vector<int>> memo(m, vector<int>(n));
int d[5] = {1,0,-1,0,1};
function<int(int,int)> dfs = [&](int r, int c) {
if (memo[r][c]) return memo[r][c];
int best = 1;
for (int k=0;k<4;k++) {
int nr=r+d[k], nc=c+d[k+1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&matrix[nr][nc]>matrix[r][c]) best=max(best,1+dfs(nr,nc));
}
return memo[r][c]=best;
};
int ans=0;
for (int r=0;r<m;r++) for (int c=0;c<n;c++) ans=max(ans, dfs(r,c));
return ans;
}
};Java
class Solution {
int[][] memo;
int[][] matrix;
int[] d = {1,0,-1,0,1};
public int longestIncreasingPath(int[][] matrix) {
this.matrix = matrix;
memo = new int[matrix.length][matrix[0].length];
int ans = 0;
for (int r=0;r<matrix.length;r++) for (int c=0;c<matrix[0].length;c++) ans = Math.max(ans, dfs(r,c));
return ans;
}
private int dfs(int r, int c) {
if (memo[r][c] != 0) return memo[r][c];
int best = 1;
for (int k=0;k<4;k++) {
int nr=r+d[k], nc=c+d[k+1];
if (nr>=0&&nr<matrix.length&&nc>=0&&nc<matrix[0].length&&matrix[nr][nc]>matrix[r][c]) best=Math.max(best,1+dfs(nr,nc));
}
return memo[r][c] = best;
}
}套路模板 · 网格记忆化 DFS 骨架
# 网格记忆化 DFS（最长递增路径）骨架
memo = {}
def dfs(r, c):
if (r,c) in memo: return memo[(r,c)] # 命中缓存直接返回
best = 1
for nr, nc in 四邻(r, c):
if 越界: continue
if matrix[nr][nc] > matrix[r][c]: # 只走严格更大
best = max(best, 1 + dfs(nr, nc))
memo[(r,c)] = best
return best
return max(dfs(r, c) for 所有格子)复杂度
时间复杂度
O(m·n)
记忆化后每格只算一次，每次看 4 个邻居
空间复杂度
O(m·n)
memo 表 + 递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 矩阵中的最长递增路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
把每个格子当起点做 DFS：dfs(r,c)=1+max(dfs(邻居) 中比当前严格大的)，没有更大邻居则为 1。用 memo 缓存每格结果避免重算。对所有格子的 dfs 取最大值即答案。
这道题为什么用「二维动态规划」，换最直接的暴力解会差在哪？+
二维动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。