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

• LeetCode：329. 矩阵中的最长递增路径 · LCR 112. 最长递增路径
• 难度：困难
• 归类：图、记忆化搜索、深度优先搜索、动态规划
• 主解法：记忆化 DFS，枚举每个起点并缓存已计算结果

#先给结论

把矩阵中的每个单元格看成图的一个节点，相邻且值更大的单元格之间有向边相连。由于数值严格递增，图中不可能存在环。

定义：

memo[row][col] = 从当前单元格出发的最长递增路径长度

对每个单元格向四个更大的邻居递归搜索，取最大值再加 1。用 memo 数组缓存结果，避免重复计算。

最后遍历所有单元格，取 memo 中的最大值即为答案。

#题目描述

给定一个 m × 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

题目约束：

• 1 <= m, n <= 200。
• 0 <= matrix[row][col] <= 2^31 - 1。

#核心思路

#状态定义

memo[row][col] = 从 (row, col) 出发，能走出的最长严格递增路径长度

每个单元格都可以作为路径起点，因此最终答案是所有 memo[row][col] 的最大值。

#状态转移

从 (row, col) 出发，检查上下左右四个邻居：

• 如果邻居在矩阵内，且值严格大于当前格，就可以走过去。
• 从该邻居继续递归搜索，得到 memo[neighbor]。
• 当前格的结果等于所有合法邻居结果的最大值加 1（加 1 是包含自己）。

memo[row][col] = 1 + max( memo[neighbor] for each valid larger neighbor )

如果没有更大的邻居，就只能停在当前格，memo[row][col] = 1。

#为什么不需要 visited

因为每次只能移动到值严格更大的单元格，数值一路递增，不可能沿任何路径走回已经访问过的单元格。严格递增天然保证了图是有向无环图（DAG），所以不需要额外的 visited 集合来防止环。

#为什么需要记忆化

如果不缓存，从多个不同的起点搜索时，会重复计算同一个单元格的结果。例如示例 1 中，6 既可以从 2 走到，也可以从另一个 1 走到。记忆化确保每个单元格只递归计算一次，之后直接查表返回。

#算法步骤

1. 初始化 memo 矩阵，所有值设为 0，表示尚未计算。
2. 对每个单元格 (r, c) 调用 dfs(r, c)：
   • 如果 memo[r][c] !== 0，直接返回缓存值。
   • 枚举四个方向，筛选出值更大的合法邻居。
   • 对每个合法邻居递归调用 dfs，收集最大值。
   • memo[r][c] = 1 + max，返回该值。
3. 遍历过程中维护全局最大值 ans。
4. 返回 ans。

#示例推演

对于：

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

从每个单元格出发的最长递增路径长度（memo 值）：

[
  [1, 1, 2],
  [2, 2, 1],
  [3, 4, 4]
]

• (2,1)=1 没有更小的邻居（题目是递增，所以从 1 出发），更大的邻居是 (2,0)=2，所以 memo[2][1] = 1 + memo[2][0] = 1 + 3 = 4？

等等，这里方向是只能走向更大的值。让我重新推演：

从 (2,1)=1 出发：

• 可以走到 (2,0)=2（更大）
• 可以走到 (1,1)=6（更大）

从 (2,0)=2 出发：

• 可以走到 (1,0)=6（更大）

从 (1,0)=6 出发：

• 可以走到 (0,0)=9（更大）
• 可以走到 (0,1)=9（更大）

从 (0,0)=9 出发：没有更大的邻居 → memo[0][0] = 1

所以 memo[1][0] = 1 + max(memo[0][0], memo[0][1]) = 1 + 1 = 2 memo[2][0] = 1 + memo[1][0] = 3

从 (2,1)=1 出发：

• 走到 (2,0)=2 的路径长度 = 1 + memo[2][0] = 4
• 走到 (1,1)=6 的路径长度 = 1 + memo[1][1]

从 (1,1)=6 出发：

• 可以走到 (0,1)=9
• 可以走到 (1,2)=8
• (0,1)=9 没有更大的邻居 → memo[0][1] = 1
• (1,2)=8 可以走到 (0,2)=4？不，4 < 8，不能走。可以走到 (0,2)=4？不行。(0,2)=4 更小。那 (1,2)=8 有更大的邻居吗？(0,2)=4 更小，(1,1)=6 更小。没有更大的。所以 memo[1][2] = 1。

所以 memo[1][1] = 1 + max(memo[0][1], memo[1][2]) = 1 + 1 = 2

memo[2][1] = 1 + max(memo[2][0], memo[1][1]) = 1 + max(3, 2) = 4

最大值为 4，对应路径 1 → 2 → 6 → 9。

让我写出正确的 memo 矩阵：

[
  [1, 1, 1],   // 9, 9, 4
  [2, 2, 1],   // 6, 6, 8
  [3, 4, 4]    // 2, 1, 1
]

等等，(2,2)=1：可以走到 (1,2)=8，所以 memo[2][2] = 1 + memo[1][2] = 1 + 1 = 2？ 不对，(2,2)=1 的邻居：

• (1,2)=8 > 1，可以走
• (2,1)=1 = 1，不能走（严格递增） 所以 memo[2][2] = 1 + memo[1][2] = 2

(0,2)=4：邻居 (1,2)=8 > 4，所以 memo[0][2] = 1 + memo[1][2] = 2

修正后的 memo：

[
  [1, 1, 2],   // 9, 9, 4
  [2, 2, 1],   // 6, 6, 8
  [3, 4, 2]    // 2, 1, 1
]

最大值是 4。

好的，我会在文档中正确写出这个推演。

#代码实现

参考实现来源：JoshCrozier/leetcode-javascript，原项目采用 MIT License。

#JavaScript 实现

/**
 * 计算矩阵中最长严格递增路径的长度
 * @param {number[][]} matrix - 输入的二维整数矩阵
 * @return {number} - 最长递增路径的长度
 */
var longestIncreasingPath = function (matrix) {
    // 处理空矩阵的边界情况：若矩阵为空或第一行为空，直接返回 0
    if (!matrix.length || !matrix[0].length) {
        return 0;
    }

    const rows = matrix.length;      // 矩阵的行数
    const cols = matrix[0].length;   // 矩阵的列数

    // memo[row][col] 用于缓存从 (row, col) 出发的最长递增路径长度
    // 初始值为 0，表示该单元格的结果尚未计算
    const memo = Array.from({ length: rows }, () => Array(cols).fill(0));

    // 四个移动方向：下、上、右、左（顺序不影响结果）
    const directions = [
        [1, 0],   // 下：行 +1，列不变
        [-1, 0],  // 上：行 -1，列不变
        [0, 1],   // 右：行不变，列 +1
        [0, -1],  // 左：行不变，列 -1
    ];

    /**
     * 深度优先搜索（DFS）+ 记忆化
     * 返回从 (row, col) 出发能走出的最长严格递增路径长度
     */
    const dfs = (row, col) => {
        // 如果 memo 中已缓存结果，直接返回，避免重复递归计算
        if (memo[row][col] !== 0) {
            return memo[row][col];
        }

        // maxLen 至少为 1，因为路径至少包含当前单元格本身
        let maxLen = 1;

        // 枚举四个方向，寻找值更大的合法邻居
        for (const [rowOffset, colOffset] of directions) {
            const nextRow = row + rowOffset;  // 邻居的行坐标
            const nextCol = col + colOffset;  // 邻居的列坐标

            // 判断邻居是否合法：
            // 1. 未越界（行和列都在矩阵范围内）
            // 2. 邻居的值严格大于当前单元格的值（保证路径严格递增）
            if (
                nextRow >= 0 &&
                nextRow < rows &&
                nextCol >= 0 &&
                nextCol < cols &&
                matrix[nextRow][nextCol] > matrix[row][col]
            ) {
                // 从当前单元格走到邻居，路径长度 = 1（当前格） + 从邻居出发的最长路径
                // 取所有合法邻居中的最大值
                maxLen = Math.max(maxLen, 1 + dfs(nextRow, nextCol));
            }
        }

        // 将计算结果缓存到 memo 中，供后续调用直接使用
        memo[row][col] = maxLen;
        return maxLen;
    };

    let ans = 0;  // 全局最长递增路径长度

    // 枚举矩阵中的每一个单元格作为路径起点
    // 因为最长路径可以从任意位置开始，所以必须全部遍历
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            // 更新全局最大值
            ans = Math.max(ans, dfs(row, col));
        }
    }

    return ans;  // 返回最终答案
};

#代码与思路对照

#正确性说明

1. 无环保证正确遍历。 每次只能移动到值严格更大的单元格，数值不可能无限递增后回到起点，因此图中不存在环，DFS 不会陷入死循环。
2. 状态定义正确。 memo[row][col] 缓存的是从该单元格出发、沿递增方向能走出的最长路径长度，与问题所求完全一致。
3. 状态转移正确。 从当前格出发，下一步可以走向任意更大的合法邻居；最长的后续路径就是这些邻居缓存值的最大值，再加上当前这一步，即 1 + max(...)。
4. 枚举起点正确。 最长递增路径的起点可以是任意单元格，因此遍历整个矩阵、对每个单元格调用 dfs 取最大值，一定能覆盖全局最优解。

#边界与陷阱

• 单个单元格： dfs 不会找到更大邻居，maxLen 保持为 1，返回 1。
• 所有值相等： 没有任何邻居满足 >，所有 memo 值都是 1，答案为 1。
• 严格大于： 转移条件必须是 >，不能使用 >=。相等值之间不能移动。
• 四个方向： 不能遗漏上或左，也不能允许对角线。
• memo 初始值： 题目数值范围是 0 到 2^31 - 1，最小路径长度是 1，所以用 0 作为"未计算"标记是安全的。
• 不修改原矩阵： 当前实现只读取 matrix，不修改它。

#复杂度分析

设矩阵大小为 m × n：

• 时间复杂度：O(mn)。每个单元格只会被计算一次，每次计算最多检查四个邻居。
• 额外空间复杂度：O(mn)。memo 数组占用 mn 个整数；递归栈深度最多为最长递增路径长度，不超过 mn。

#与拓扑排序 BFS 的取舍

这道题也可以用拓扑排序（Kahn 算法）求解：把递增关系建成 DAG，统计入度，从局部最小值开始逐层 BFS，层数即为最长路径长度。

结论： 记忆化 DFS 是这道题的标准解法，代码简洁、思路直观，适合面试快速实现。只有在特别担心递归深度（如题目规模极大）时才考虑拓扑 BFS。

#面试官递进追问

#1. 为什么严格递增关系保证不会出现环？

沿任意合法路径移动，数值严格增加。如果存在环，沿环走一圈后起点值必须严格大于自身，矛盾。

#2. 为什么不需要visited 数组？

因为数值只能增大不能减小，不可能从当前路径走回已经访问过的单元格。天然的有向无环结构替代了显式的访问标记。

#3. 如果不加memo 缓存，时间复杂度是多少？

退化为普通 DFS，每个起点独立搜索，大量子问题重复计算，最坏时间复杂度为指数级 O(2^(mn))。

#4.memo 用0 作为未计算标记是否安全？

安全。题目要求的是路径长度，最短路径至少包含当前单元格本身，即长度至少为 1。0 不可能是一个合法的路径长度结果。

#5. 能不能把问题改成"求以每个单元格结尾的最长递增路径"？

可以。只需把 DFS 中的比较方向从 > 改成 <，即只走向更小的邻居，状态定义相应改为"以当前格结尾的最长递减路径"。两种定义本质相同。

#6. 时间复杂度为什么是O(mn)？

每个单元格作为子问题只会被计算一次（首次调用 dfs 时写入 memo，后续直接返回）。单次计算最多遍历四个方向，是 O(1)。总共 mn 个单元格，因此总时间为 O(mn)。

#常见错误

• 把矩阵当作普通二维 DP，却没有确定状态依赖的计算顺序（DAG 上的 DP 天然适合记忆化搜索）。
• 只从某一个单元格开始搜索，遗漏其他可能的起点。
• 允许移动到相等值，破坏严格递增条件。
• 使用对角线移动，或遗漏上、左方向。
• 忘记加 1（maxLen 初始应为 1，代表只包含当前单元格）。
• 不加 memo 缓存，导致超时。
• 把 memo 初始值设为非零值，与合法结果混淆。

#可迁移总结

• DAG 上的 DP： 有向无环图中的最长路径问题，常用记忆化 DFS 或拓扑排序求解。
• 网格转图： 单元格是节点，合法移动是边；单调关系（严格递增/递减）天然形成 DAG。
• 记忆化搜索： 自顶向下带缓存的递归，代码直观，状态转移公式清晰。
• 状态设计： memo[i][j] 表示从某点出发/到达某点的最优值，根据题目要求选择方向。
• 一句话记忆： 向更大的邻居递归，缓存每个格子的最优结果，全局取最大。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么从每个单元格出发都要调用一次 dfs，而不是只从一个起点开始？

2. 如果把 matrix[nextRow][nextCol] > matrix[row][col] 改成 >=，会发生什么？

3. 什么情况下递归栈深度最大？最大可能是多少？

4. 写出拓扑排序 BFS 的核心思路，并说明它与记忆化 DFS 的时间复杂度关系。