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

字数 2558 2025-10-27 17:41:11

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

题目描述
给定一个 m x n 的整数矩阵，你需要找出矩阵中最长递增路径的长度。对于每个单元格，你可以向四个方向移动：上、下、左、右。你不能在对角线方向上移动或移动到边界外。递增路径是指路径上的数字严格递增。

例如，给定矩阵：
[
[9, 9, 4],
[6, 6, 8],
[2, 1, 1]
]
最长递增路径是 [1, 2, 6, 9] 或 [1, 2, 8, 9]，长度为 4。

解题过程

这个问题本质上是在一个有向无环图中寻找最长路径，其中每个单元格是一个节点，从较小值指向较大值的边构成了有向边。由于路径必须严格递增，因此图中不可能有环。

1. 暴力深度优先搜索（DFS）的局限性
最直观的想法是对每个单元格都作为起点，进行深度优先搜索，探索所有可能的递增路径，并记录最大值。

步骤：对于当前单元格，检查其四个邻居。如果邻居的值大于当前单元格，则递归地以该邻居为新的起点继续搜索。当前路径的长度是 1（当前单元格）加上所有可能递归路径中的最大值。
问题：这种方法会进行大量的重复计算。例如，在上面的矩阵中，以“1”为起点的路径会被以“2”为起点的路径重复计算多次。时间复杂度是指数级的，无法通过较大规模的测试用例。

2. 引入记忆化（Memoization）
为了优化暴力DFS，我们引入记忆化技术，也称为“记忆化搜索”。核心思想是：用一个与矩阵同大小的缓存数组（例如 memo）来记录每个单元格作为起点的最长递增路径长度。这样，当计算到某个单元格时，如果它的结果已经被计算过，我们就可以直接返回缓存的值，避免重复递归。

3. 详细解题步骤
现在，我们结合DFS和记忆化来详细拆解算法。

步骤一：初始化
- 定义矩阵的行数 m 和列数 n。
- 创建一个大小为 m x n 的二维数组 memo，初始值全部设为0。memo[i][j] 表示以单元格 (i, j) 为起点的最长递增路径长度。
- 初始化最终结果 maxLength = 0。
步骤二：遍历每个单元格
- 我们遍历矩阵中的每一个单元格 (i, j)。
- 对每个单元格，我们都调用一个DFS函数，计算以它为起点的最长路径长度。
- maxLength 不断更新为所有DFS返回值中的最大值。
步骤三：设计DFS函数
DFS函数 dfs(i, j) 的目标是计算并返回 memo[i][j]。
- 检查缓存：首先检查 memo[i][j] 是否大于0。如果大于0，说明这个位置的结果已经计算过了，直接返回 memo[i][j]。这是记忆化减少重复计算的关键。
- 初始化当前路径长度：至少包含自己，所以初始长度 currentMax = 1。
- 探索四个方向：定义方向数组 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]，分别代表右、下、左、上。
  - 对于每个方向 (dx, dy)，计算邻居坐标 x = i + dx, y = j + dy。
  - 检查邻居有效性：检查 (x, y) 是否在矩阵边界内。
  - 检查递增条件：检查邻居的值 matrix[x][y] 是否大于当前单元格的值 matrix[i][j]。
  - 如果两个条件都满足，说明可以沿着这个方向走。我们递归调用 dfs(x, y)，得到从邻居出发能走的最长路径长度。
  - 那么，当前路径通过这个邻居能达到的长度就是 1 + dfs(x, y)（1代表当前单元格）。
  - currentMax 更新为 max(currentMax, 1 + dfs(x, y))，即取所有可能方向中的最大值。
- 更新缓存并返回：在尝试完所有方向后，将 currentMax 的值存入 memo[i][j]。最后返回 memo[i][j]。
步骤四：为什么这是有向无环图（DAG）上的动态规划？
- 有向图：边是从小值节点指向大值节点。
- 无环：因为路径严格递增，不可能走回已经走过的节点。
- 在DAG中，我们可以用动态规划求最长路径。我们的 memo 数组就是DP表，dfs 的递归过程实际上就是DP的递推过程（自顶向下带记忆化的方式）。状态转移方程为：
  memo[i][j] = max( memo[i][j], 1 + memo[x][y] ) （对于所有满足 matrix[x][y] > matrix[i][j] 的邻居 (x, y)）

举例说明
以题目中的矩阵为例：
[
[9, 9, 4],
[6, 6, 8],
[2, 1, 1]
]
我们计算以右下角 (2, 1) 的 “1” 为起点的路径：

调用 dfs(2, 1)。memo[2][1] 初始为0，开始计算。
检查四个邻居：
- 上 (1, 1)：值是6，大于1，有效。递归调用 dfs(1, 1)。
- 在 dfs(1, 1) 中，检查邻居：
  - 上 (0, 1)：值是9，大于6，有效。调用 dfs(0, 1)。
    - 在 dfs(0, 1) 中，所有邻居的值都不大于9，所以 memo[0][1] = 1。
  - 右 (1, 2)：值是8，大于6，有效。调用 dfs(1, 2)。
    - 在 dfs(1, 2) 中，所有邻居的值都不大于8，所以 memo[1][2] = 1。
  - memo[1][1] = 1 + max( dfs(0,1), dfs(1,2) ) = 1 + max(1, 1) = 2。
- 所以 dfs(1, 1) 返回2。
- 因此，通过“上”方向，路径长度为 1 + 2 = 3。
- 其他方向（下、左、右）要么越界，要么值不大于1。
currentMax = max(1, 3) = 3。所以 memo[2][1] = 3。
最终，通过遍历所有点，我们会发现最长路径是4（例如从 (2, 1) 的1 -> (2, 0) 的2 -> (1, 0) 的6 -> (0, 0) 的9）。这个结果会在计算其他起点时被找到并记录。

LeetCode 329. 矩阵中的最长递增路径题目描述给定一个 m x n 的整数矩阵，你需要找出矩阵中最长递增路径的长度。对于每个单元格，你可以向四个方向移动：上、下、左、右。你不能在对角线方向上移动或移动到边界外。递增路径是指路径上的数字严格递增。例如，给定矩阵： [ [ 9, 9, 4 ], [ 6, 6, 8 ], [ 2, 1, 1 ] ] 最长递增路径是 [ 1, 2, 6, 9] 或 [ 1, 2, 8, 9 ]，长度为 4。解题过程这个问题本质上是在一个有向无环图中寻找最长路径，其中每个单元格是一个节点，从较小值指向较大值的边构成了有向边。由于路径必须严格递增，因此图中不可能有环。 1. 暴力深度优先搜索（DFS）的局限性最直观的想法是对每个单元格都作为起点，进行深度优先搜索，探索所有可能的递增路径，并记录最大值。步骤：对于当前单元格，检查其四个邻居。如果邻居的值大于当前单元格，则递归地以该邻居为新的起点继续搜索。当前路径的长度是 1（当前单元格）加上所有可能递归路径中的最大值。问题：这种方法会进行大量的重复计算。例如，在上面的矩阵中，以“1”为起点的路径会被以“2”为起点的路径重复计算多次。时间复杂度是指数级的，无法通过较大规模的测试用例。 2. 引入记忆化（Memoization）为了优化暴力DFS，我们引入记忆化技术，也称为“记忆化搜索”。核心思想是：用一个与矩阵同大小的缓存数组（例如 memo ）来记录每个单元格作为起点的最长递增路径长度。这样，当计算到某个单元格时，如果它的结果已经被计算过，我们就可以直接返回缓存的值，避免重复递归。 3. 详细解题步骤现在，我们结合DFS和记忆化来详细拆解算法。步骤一：初始化定义矩阵的行数 m 和列数 n 。创建一个大小为 m x n 的二维数组 memo ，初始值全部设为0。 memo[i][j] 表示以单元格 (i, j) 为起点的最长递增路径长度。初始化最终结果 maxLength = 0 。步骤二：遍历每个单元格我们遍历矩阵中的每一个单元格 (i, j) 。对每个单元格，我们都调用一个DFS函数，计算以它为起点的最长路径长度。 maxLength 不断更新为所有DFS返回值中的最大值。步骤三：设计DFS函数 DFS函数 dfs(i, j) 的目标是计算并返回 memo[i][j] 。检查缓存：首先检查 memo[i][j] 是否大于0。如果大于0，说明这个位置的结果已经计算过了，直接返回 memo[i][j] 。这是记忆化减少重复计算的关键。初始化当前路径长度：至少包含自己，所以初始长度 currentMax = 1 。探索四个方向：定义方向数组 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] ，分别代表右、下、左、上。对于每个方向 (dx, dy) ，计算邻居坐标 x = i + dx , y = j + dy 。检查邻居有效性：检查 (x, y) 是否在矩阵边界内。检查递增条件：检查邻居的值 matrix[x][y] 是否大于当前单元格的值 matrix[i][j] 。如果两个条件都满足，说明可以沿着这个方向走。我们递归调用 dfs(x, y) ，得到从邻居出发能走的最长路径长度。那么，当前路径通过这个邻居能达到的长度就是 1 + dfs(x, y) （1代表当前单元格）。 currentMax 更新为 max(currentMax, 1 + dfs(x, y)) ，即取所有可能方向中的最大值。更新缓存并返回：在尝试完所有方向后，将 currentMax 的值存入 memo[i][j] 。最后返回 memo[i][j] 。步骤四：为什么这是有向无环图（DAG）上的动态规划？有向图：边是从小值节点指向大值节点。无环：因为路径严格递增，不可能走回已经走过的节点。在DAG中，我们可以用动态规划求最长路径。我们的 memo 数组就是DP表， dfs 的递归过程实际上就是DP的递推过程（自顶向下带记忆化的方式）。状态转移方程为： memo[i][j] = max( memo[i][j], 1 + memo[x][y] ) （对于所有满足 matrix[x][y] > matrix[i][j] 的邻居 (x, y) ）举例说明以题目中的矩阵为例： [ [ 9, 9, 4 ], [ 6, 6, 8 ], [ 2, 1, 1 ] ] 我们计算以右下角 (2, 1) 的 “1” 为起点的路径：调用 dfs(2, 1) 。 memo[2][1] 初始为0，开始计算。检查四个邻居：上 (1, 1)：值是6，大于1，有效。递归调用 dfs(1, 1) 。在 dfs(1, 1) 中，检查邻居：上 (0, 1)：值是9，大于6，有效。调用 dfs(0, 1) 。在 dfs(0, 1) 中，所有邻居的值都不大于9，所以 memo[0][1] = 1 。右 (1, 2)：值是8，大于6，有效。调用 dfs(1, 2) 。在 dfs(1, 2) 中，所有邻居的值都不大于8，所以 memo[1][2] = 1 。 memo[1][1] = 1 + max( dfs(0,1), dfs(1,2) ) = 1 + max(1, 1) = 2 。所以 dfs(1, 1) 返回2。因此，通过“上”方向，路径长度为 1 + 2 = 3 。其他方向（下、左、右）要么越界，要么值不大于1。 currentMax = max(1, 3) = 3 。所以 memo[2][1] = 3 。最终，通过遍历所有点，我们会发现最长路径是4（例如从 (2, 1) 的1 -> (2, 0) 的2 -> (1, 0) 的6 -> (0, 0) 的9）。这个结果会在计算其他起点时被找到并记录。