线性动态规划：最长递增路径

题目描述

给定一个二维整数矩阵 matrix，其大小为 m x n。你需要找到矩阵中的最长递增路径的长度。对于每个单元格，你可以向四个方向移动：上、下、左、右。但不能移动到边界外，也不能移动到值小于或等于当前单元格的位置（路径必须是严格递增的）。换句话说，你需要找到一条在矩阵中严格递增的路径，并返回其包含的单元格数量。

示例1:

输入: matrix = [
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]
输出: 4
解释: 最长递增路径是 [1, 2, 6, 9]，长度为4。路径方向可以是: 1 -> 2 -> 6 -> 9，但注意1在(2,1)，2在(0,2)是跳跃的，实际路径是连续移动的，比如 1(2,1) -> 2(2,0) -> 6(1,0) -> 9(0,0)。

示例2:

输入: matrix = [
  [3, 4, 5],
  [3, 2, 6],
  [2, 2, 1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]，长度为4。

注意:

• 你不能在对角线方向移动。
• 路径必须严格递增，即下一个单元格的值必须严格大于当前单元格的值。

解题过程

这是一个典型的记忆化搜索（Memoization）结合动态规划的问题，也可以视为基于拓扑排序的动态规划。核心思路是：对于每个单元格 (i, j)，计算以该单元格为起点的最长递增路径长度。因为路径是严格递增的，所以不会形成环，我们可以通过深度优先搜索（DFS）递归计算，并使用一个缓存数组记录已经计算过的结果，避免重复计算。

步骤1：定义状态与子问题

定义 dp[i][j] 表示以矩阵中位置 (i, j) 为起点的最长递增路径的长度。

• 如果从 (i, j) 出发，无法向任何方向移动（即四个相邻单元格的值都不大于当前值），那么 dp[i][j] = 1（路径只包含自己）。
• 否则，dp[i][j] 等于 1 加上所有可移动方向的邻居中 dp 值的最大值。

子问题：计算 dp[i][j] 需要先计算其所有值更大的邻居的 dp 值。由于路径严格递增，依赖关系不会形成环，因此可以通过DFS递归求解。

步骤2：状态转移方程

设 matrix[i][j] 的值为 val。对于四个方向 (dx, dy)（上下左右），如果邻居 (ni, nj) 在矩阵范围内且 matrix[ni][nj] > val，则可以从 (i, j) 移动到 (ni, nj)。
状态转移方程为：

dp[i][j] = 1 + max{ dp[ni][nj] | (ni, nj) 是四个方向中值大于 val 的邻居 }

如果没有任何符合条件的邻居，则 dp[i][j] = 1。

步骤3：计算顺序与记忆化

直接按任意顺序计算可能会重复递归。我们采用记忆化搜索（Memoization）：

• 初始化一个与矩阵同尺寸的数组 dp，所有值设为0（表示未计算）。
• 对每个单元格 (i, j)，如果 dp[i][j] 未计算（为0），则调用DFS函数计算它。
• 在DFS函数中，先检查 dp[i][j] 是否已计算，若是则直接返回。
• 否则，遍历四个方向，对每个值大于当前值的邻居，递归计算其 dp 值，然后更新 dp[i][j] 为 1 + 最大邻居dp值。
• 最终答案为所有 dp[i][j] 中的最大值。

步骤4：算法细节

1. 方向数组：dirs = [(0,1), (1,0), (0,-1), (-1,0)] 表示右、下、左、上。
2. DFS函数 dfs(i, j)：
   • 如果 dp[i][j] != 0，直接返回 dp[i][j]。
   • 初始化 best = 1（至少包含自己）。
   • 遍历四个方向，计算邻居坐标 (ni, nj)。
   • 如果邻居在矩阵内且 matrix[ni][nj] > matrix[i][j]，则 best = max(best, 1 + dfs(ni, nj))。
   • 更新 dp[i][j] = best 并返回。
3. 主函数：遍历所有 (i, j)，调用 dfs(i, j) 并更新全局最大长度。

步骤5：示例推演

以示例1的矩阵为例：

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

我们计算部分关键点的 dp 值：

• 从右下角 (2,2) 值1开始，邻居都小于等于1，所以 dp[2][2] = 1。
• 对于 (2,1) 值1，邻居 (2,2) 值为1（不大于），(1,1) 值为6（大于），所以递归计算 (1,1)。
  • (1,1) 值6，邻居 (0,1) 值9（大于），递归计算 (0,1)。
    • (0,1) 值9，没有更大值的邻居，dp[0][1] = 1。
  • 所以 dp[1][1] = 1 + dp[0][1] = 2。
  • 回溯到 (2,1)，dp[2][1] = 1 + dp[1][1] = 3。
• 类似地，(2,0) 值2，邻居 (1,0) 值6（大于），递归计算 (1,0) 得到 dp[1,0] = 1 + dp[0,0] = 2（因为 (0,0) 值9是邻居且更大，但 (0,0) 的 dp=1）。所以 dp[2,0] = 1 + 2 = 3。
• 最终，全局最大值出现在 (2,1) 或 (2,0)，值为4（路径 1->6->9 或 2->6->9 加上起点自身，长度4）。

步骤6：复杂度分析

• 时间复杂度：O(m * n)。每个单元格计算一次，每次计算检查四个方向，总操作 O(4 * m * n) = O(m * n)。
• 空间复杂度：O(m * n) 用于存储 dp 数组，递归栈深度最多 O(m * n) 但通常远小于。

步骤7：代码实现（Python风格伪代码）

def longestIncreasingPath(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]  # 记忆化数组
    dirs = [(0,1), (1,0), (0,-1), (-1,0)]
    
    def dfs(i, j):
        if dp[i][j] != 0:
            return dp[i][j]
        best = 1
        for dx, dy in dirs:
            ni, nj = i + dx, j + dy
            if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                best = max(best, 1 + dfs(ni, nj))
        dp[i][j] = best
        return best
    
    ans = 0
    for i in range(m):
        for j in range(n):
            ans = max(ans, dfs(i, j))
    return ans

总结

本题通过定义状态 dp[i][j] 为以 (i, j) 为起点的最长递增路径长度，利用记忆化搜索避免了重复计算。由于路径严格递增，依赖关系无环，因此DFS可以正确求解。最终答案为所有 dp[i][j] 的最大值。这是二维矩阵中经典的长递增路径问题，结合了DFS和动态规划的思想。