329. 矩阵中的最长递增路径

🔴   🔖  深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 数组 动态规划 矩阵  🔗 力扣 LeetCode

题目

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output: 4

Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]

Output: 1

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 2^31 - 1

题目大意

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外 （即不允许环绕）。

示例 1：

输入： matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出： 4

解释： 最长递增路径为  [1, 2, 6, 9]。

示例 2：

输入： matrix = [[3,4,5],[3,2,6],[2,2,1]]

输出： 4

解释： 最长递增路径是  [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入： matrix = [[1]]

输出： 1

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 2^31 - 1

解题思路

使用 记忆化搜索 + DFS（深度优先搜索） 进行求解：

1. 定义 dp[i][j]：表示从 (i, j) 位置出发的最长递增路径。
2. 递归搜索 dfs(x, y)：
   • 如果 dp[x][y] 已经计算过，则直接返回 dp[x][y]。
   • 否则，枚举四个方向 (dx, dy)，如果新位置 (nx, ny) 处的值 matrix[nx][ny] > matrix[x][y]，递归计算 dfs(nx, ny) 并更新 dp[x][y]。
   • 最终 dp[x][y] = max(所有可能路径长度) + 1。
3. 遍历整个矩阵，计算每个 dp[i][j] 的最大值，即为答案。

复杂度分析

• 时间复杂度：O(m * n)，每个单元格最多计算一次，记忆化避免重复计算。
• 空间复杂度：O(m * n)，用于 dp 数组的存储。

代码

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function (matrix) {
	const m = matrix.length;
	const n = matrix[0].length;
	const dp = new Array(m).fill().map(() => new Array(n).fill(0));
	let maxDepth = 1;

	const dfs = (x, y) => {
		if (dp[x][y] > 0) {
			return dp[x][y];
		}
		let depth = 1;
		const dirc = [
			[1, 0],
			[-1, 0],
			[0, 1],
			[0, -1]
		];
		for (let [dx, dy] of dirc) {
			const nx = x + dx;
			const ny = y + dy;
			if (
				nx >= 0 &&
				nx < m &&
				ny >= 0 &&
				ny < n &&
				matrix[nx][ny] > matrix[x][y]
			) {
				depth = Math.max(depth, dfs(nx, ny) + 1);
			}
		}
		dp[x][y] = depth;
		return depth;
	};
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			maxDepth = Math.max(maxDepth, dfs(i, j));
		}
	}
	return maxDepth;
};

相关题目

题号	标题	题解	标签	难度	力扣
2328	网格图中递增路径的数目		深度优先搜索 广度优先搜索 图 5+	🔴	🀄️ 🔗