线性动态规划：二维最长递增路径（Longest Increasing Path in a Matrix）

字数 1964 2025-12-13 05:15:51

线性动态规划：二维最长递增路径（Longest Increasing Path in a Matrix）

问题描述

给定一个 \(m \times n\) 的整数矩阵 matrix，你需要找到矩阵中最长的递增路径的长度。在路径中，每一步你可以从当前单元格移动到上、下、左、右四个相邻单元格之一，但要求移动后的单元格数值严格大于当前单元格的数值。路径长度定义为路径上经过的单元格数目。

示例

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

最长递增路径可以是 1 → 2 → 6 → 9（长度为 4），或 1 → 6 → 9（长度为 3）等。但最长长度为 4。

解题思路

这是一个典型的记忆化搜索（Memoization）问题，属于线性动态规划的变种（因为路径长度依赖相邻状态，且存在重叠子问题）。
暴力搜索会重复计算大量子路径，因此我们使用动态规划表格 dp[i][j] 记录以单元格 (i, j) 为起点的最长递增路径长度。
关键点：路径是严格递增的，因此不会形成环，保证了动态规划的无后效性。

详细解题步骤

步骤 1：定义状态

令 dp[i][j] 表示以矩阵中第 i 行、第 j 列元素为起点的最长递增路径的长度。

初始时，每个单元格至少可以停留在自己位置，所以最小长度为 1。

步骤 2：状态转移方程

对于单元格 (i, j)，我们尝试向四个方向（上、下、左、右）移动：

如果相邻单元格 (ni, nj) 的值大于 matrix[i][j]，那么可以从 (i, j) 走到 (ni, nj)，从而将路径长度扩展为 1 + dp[ni][nj]。
因此，状态转移为：

\[dp[i][j] = \max_{\text{相邻单元格且值更大}} (1 + dp[ni][nj]) \]

如果没有符合条件的相邻单元格，则 dp[i][j] = 1。

步骤 3：计算顺序

由于状态 dp[i][j] 依赖相邻且值更大的单元格的状态，我们不能简单地按行或列顺序计算。
一种有效的方法是深度优先搜索（DFS）配合记忆化：

对于每个单元格 (i, j)，如果 dp[i][j] 尚未计算，就递归计算其四个邻居中值更大的单元格的 dp 值。

步骤 4：记忆化搜索实现

初始化 dp 为全 0，表示未计算。
遍历矩阵每个单元格 (i, j)，调用 DFS 函数计算 dp[i][j]。
在 DFS 函数中：
- 如果当前 dp[i][j] 已计算，直接返回。
- 否则，初始设置长度为 1。
- 遍历四个方向：
  - 检查邻居 (ni, nj) 是否在矩阵范围内，且 matrix[ni][nj] > matrix[i][j]。
  - 递归计算 dp[ni][nj]。
  - 更新当前长度为 max(当前长度, 1 + dp[ni][nj])。
- 保存结果到 dp[i][j] 并返回。

步骤 5：最终答案

最终答案为所有 dp[i][j] 中的最大值。

举例说明（以示例矩阵为例）

矩阵：

9 9 4
6 6 8
2 1 1

从 (2, 1)（值为 1）开始：
- 邻居 (1, 1)（值为 6）更大，递归计算 (1, 1)。
  - (1, 1) 邻居 (0, 1)（值为 9）更大，递归计算 (0, 1)。
    - (0, 1) 没有更大的邻居，dp=1。
  - 所以 (1, 1) 的 dp = 1 + dp[0][1] = 2。
- 回到 (2, 1)：dp = 1 + dp[1][1] = 3。
- 另外，(2, 1) 的邻居 (2, 0)（值为 2）更大，递归计算 (2, 0)。
  - (2, 0) 邻居 (1, 0)（值为 6）更大，递归计算 (1, 0)。
    - (1, 0) 邻居 (0, 0)（值为 9）更大，递归计算 (0, 0)。
      - (0, 0) 无更大邻居，dp=1。
    - (1, 0) 的 dp = 1 + dp[0][0] = 2。
  - (2, 0) 的 dp = 1 + dp[1][0] = 3。
- 所以 (2, 1) 最终 dp = max(3, 1+3) = 4。
以此类推，最终得到全局最长路径为 4。

复杂度分析

时间复杂度：O(m × n)。每个单元格的 dp 值只计算一次，每次计算最多检查四个邻居。
空间复杂度：O(m × n) 用于存储 dp 表，递归栈深度最多 O(m × n) 但通常较小。

关键点总结

由于路径严格递增，图是无环的，保证了动态规划的正确性。
记忆化搜索避免了重复计算。
方向数组 dirs = [(0,1), (0,-1), (1,0), (-1,0)] 简化了邻居遍历。

线性动态规划：二维最长递增路径（Longest Increasing Path in a Matrix）问题描述给定一个 \( m \times n \) 的整数矩阵 matrix ，你需要找到矩阵中最长的递增路径的长度。在路径中，每一步你可以从当前单元格移动到上、下、左、右四个相邻单元格之一，但要求移动后的单元格数值严格大于当前单元格的数值。路径长度定义为路径上经过的单元格数目。示例最长递增路径可以是 1 → 2 → 6 → 9 （长度为 4），或 1 → 6 → 9 （长度为 3）等。但最长长度为 4。解题思路这是一个典型的记忆化搜索（Memoization）问题，属于线性动态规划的变种（因为路径长度依赖相邻状态，且存在重叠子问题）。暴力搜索会重复计算大量子路径，因此我们使用动态规划表格 dp[i][j] 记录以单元格 (i, j) 为起点的最长递增路径长度。关键点：路径是严格递增的，因此不会形成环，保证了动态规划的无后效性。详细解题步骤步骤 1：定义状态令 dp[i][j] 表示以矩阵中第 i 行、第 j 列元素为起点的最长递增路径的长度。初始时，每个单元格至少可以停留在自己位置，所以最小长度为 1。步骤 2：状态转移方程对于单元格 (i, j) ，我们尝试向四个方向（上、下、左、右）移动：如果相邻单元格 (ni, nj) 的值大于 matrix[i][j] ，那么可以从 (i, j) 走到 (ni, nj) ，从而将路径长度扩展为 1 + dp[ni][nj] 。因此，状态转移为： \[ dp[ i][ j] = \max_ {\text{相邻单元格且值更大}} (1 + dp[ ni][ nj ]) \] 如果没有符合条件的相邻单元格，则 dp[i][j] = 1 。步骤 3：计算顺序由于状态 dp[i][j] 依赖相邻且值更大的单元格的状态，我们不能简单地按行或列顺序计算。一种有效的方法是深度优先搜索（DFS）配合记忆化：对于每个单元格 (i, j) ，如果 dp[i][j] 尚未计算，就递归计算其四个邻居中值更大的单元格的 dp 值。步骤 4：记忆化搜索实现初始化 dp 为全 0，表示未计算。遍历矩阵每个单元格 (i, j) ，调用 DFS 函数计算 dp[i][j] 。在 DFS 函数中：如果当前 dp[i][j] 已计算，直接返回。否则，初始设置长度为 1。遍历四个方向：检查邻居 (ni, nj) 是否在矩阵范围内，且 matrix[ni][nj] > matrix[i][j] 。递归计算 dp[ni][nj] 。更新当前长度为 max(当前长度, 1 + dp[ni][nj]) 。保存结果到 dp[i][j] 并返回。步骤 5：最终答案最终答案为所有 dp[i][j] 中的最大值。举例说明（以示例矩阵为例）矩阵：从 (2, 1) （值为 1）开始：邻居 (1, 1) （值为 6）更大，递归计算 (1, 1) 。 (1, 1) 邻居 (0, 1) （值为 9）更大，递归计算 (0, 1) 。 (0, 1) 没有更大的邻居， dp=1 。所以 (1, 1) 的 dp = 1 + dp[0][1] = 2 。回到 (2, 1) ： dp = 1 + dp[1][1] = 3 。另外， (2, 1) 的邻居 (2, 0) （值为 2）更大，递归计算 (2, 0) 。 (2, 0) 邻居 (1, 0) （值为 6）更大，递归计算 (1, 0) 。 (1, 0) 邻居 (0, 0) （值为 9）更大，递归计算 (0, 0) 。 (0, 0) 无更大邻居， dp=1 。 (1, 0) 的 dp = 1 + dp[0][0] = 2 。 (2, 0) 的 dp = 1 + dp[1][0] = 3 。所以 (2, 1) 最终 dp = max(3, 1+3) = 4 。以此类推，最终得到全局最长路径为 4。复杂度分析时间复杂度：O(m × n)。每个单元格的 dp 值只计算一次，每次计算最多检查四个邻居。空间复杂度：O(m × n) 用于存储 dp 表，递归栈深度最多 O(m × n) 但通常较小。关键点总结由于路径严格递增，图是无环的，保证了动态规划的正确性。记忆化搜索避免了重复计算。方向数组 dirs = [(0,1), (0,-1), (1,0), (-1,0)] 简化了邻居遍历。