LeetCode 329: Longest Increasing Path in a Matrix (DFS + Memoization)
LeetCode 329DFSMemoizationToday we solve LeetCode 329 - Longest Increasing Path in a Matrix.
Source: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
English
Problem Summary
Given an m x n integer matrix, you can move in 4 directions. Find the length of the longest strictly increasing path.
Key Insight
Direct edges from a cell to larger neighbors form a DAG, because values strictly increase along any valid move. So for each cell, the answer is:
dp[r][c] = 1 + max(dp[nr][nc]) over neighbors with larger values. Use DFS + memoization to compute each state once.
Algorithm
- For every cell, run DFS to compute longest path starting there.
- If already memoized, return cached value.
- Try 4 neighbors; only continue when neighbor value is larger.
- Save best length in memo and update global maximum.
Complexity Analysis
Time: O(mn).
Space: O(mn) for memo + recursion stack in worst case.
Common Pitfalls
- Forgetting memoization, causing exponential repeated DFS.
- Allowing non-strict move (>= instead of >).
- Mixing row/column boundaries in neighbor traversal.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
private int[][] matrix;
private int[][] memo;
private int m, n;
public int longestIncreasingPath(int[][] matrix) {
this.matrix = matrix;
m = matrix.length;
n = matrix[0].length;
memo = new int[m][n];
int ans = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; 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[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (matrix[nr][nc] > matrix[r][c]) {
best = Math.max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
}var dirs = [][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 i := range memo {
memo[i] = make([]int, n)
}
var dfs func(int, int) int
dfs = func(r, c int) int {
if memo[r][c] != 0 {
return memo[r][c]
}
best := 1
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
continue
}
if matrix[nr][nc] > matrix[r][c] {
best = max(best, 1+dfs(nr, nc))
}
}
memo[r][c] = best
return best
}
ans := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
ans = max(ans, dfs(r, c))
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
a = &matrix;
memo.assign(m, vector<int>(n, 0));
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;
}
private:
int m, n;
vector<vector<int>>* a;
vector<vector<int>> memo;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
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 + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if ((*a)[nr][nc] > (*a)[r][c]) {
best = max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
};class Solution:
def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
m, n = len(matrix), len(matrix[0])
memo = [[0] * n for _ in range(m)]
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int) -> int:
if memo[r][c] != 0:
return memo[r][c]
best = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[r][c] = best
return best
ans = 0
for r in range(m):
for c in range(n):
ans = max(ans, dfs(r, c))
return ansconst DIRS = [[1,0],[-1,0],[0,1],[0,-1]];
var longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const memo = Array.from({ length: m }, () => Array(n).fill(0));
function dfs(r, c) {
if (memo[r][c] !== 0) return memo[r][c];
let best = 1;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (matrix[nr][nc] > matrix[r][c]) {
best = Math.max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
let ans = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
ans = Math.max(ans, dfs(r, c));
}
}
return ans;
};中文
题目概述
给定一个 m x n 整数矩阵，每一步可向上下左右移动一格，要求找到最长的严格递增路径长度。
核心思路
把每个格子看成节点，只从小值连向大值邻居，会形成有向无环图（DAG）。因此可定义：
dp[r][c] = 1 + max(dp[nr][nc])（邻居值更大时）。用 DFS + 记忆化即可避免重复计算。
算法步骤
- 遍历每个格子，计算“从该格子出发”的最长递增路径。
- 若该格子已有记忆值，直接返回。
- 尝试 4 个方向，只向更大的邻居继续 DFS。
- 写回记忆数组，并更新全局最大值。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(mn)（记忆数组 + 递归栈）。
常见陷阱
- 不做记忆化会导致大量重复 DFS，性能爆炸。
- 条件写成 >= 会破坏“严格递增”要求。
- 邻居越界判断写错，容易下标异常。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
private int[][] matrix;
private int[][] memo;
private int m, n;
public int longestIncreasingPath(int[][] matrix) {
this.matrix = matrix;
m = matrix.length;
n = matrix[0].length;
memo = new int[m][n];
int ans = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; 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[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (matrix[nr][nc] > matrix[r][c]) {
best = Math.max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
}var dirs = [][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 i := range memo {
memo[i] = make([]int, n)
}
var dfs func(int, int) int
dfs = func(r, c int) int {
if memo[r][c] != 0 {
return memo[r][c]
}
best := 1
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
continue
}
if matrix[nr][nc] > matrix[r][c] {
best = max(best, 1+dfs(nr, nc))
}
}
memo[r][c] = best
return best
}
ans := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
ans = max(ans, dfs(r, c))
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
a = &matrix;
memo.assign(m, vector<int>(n, 0));
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;
}
private:
int m, n;
vector<vector<int>>* a;
vector<vector<int>> memo;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
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 + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if ((*a)[nr][nc] > (*a)[r][c]) {
best = max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
};class Solution:
def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
m, n = len(matrix), len(matrix[0])
memo = [[0] * n for _ in range(m)]
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int) -> int:
if memo[r][c] != 0:
return memo[r][c]
best = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[r][c] = best
return best
ans = 0
for r in range(m):
for c in range(n):
ans = max(ans, dfs(r, c))
return ansconst DIRS = [[1,0],[-1,0],[0,1],[0,-1]];
var longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const memo = Array.from({ length: m }, () => Array(n).fill(0));
function dfs(r, c) {
if (memo[r][c] !== 0) return memo[r][c];
let best = 1;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (matrix[nr][nc] > matrix[r][c]) {
best = Math.max(best, 1 + dfs(nr, nc));
}
}
memo[r][c] = best;
return best;
}
let ans = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
ans = Math.max(ans, dfs(r, c));
}
}
return ans;
};
Comments