📃 题目描述

题目链接：

• 剑指 Offer II 112. 最长递增路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 329. 矩阵中的最长递增路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个 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]。注意不允许在对角线方向上移动。

🔔 解题思路

有向无环图（因为每条路径中下一个节点的值一定得是大于上一个节点的），不需要 visited 数组

解决图搜索通常用广度优先搜索和深度优先搜索这两种不同的方法。这个问题中的路径是非常关键的信息，而深度优先搜索能够很方便地记录搜索的路径，因此深度优先搜索更适合这个问题。

朴素深度优先搜索

直接套模板，DFS 每一个数字，然后找到以此数字为起点的最长递增路径的长度，很容易写出以下的代码：

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        // 存储最长递增路径的长度
        int res = 0;

        for (int i = 0; i < matrix.length; i ++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                int length = dfs(matrix, i, j);
                res = Math.max(res, length);
            }
        }

        return res;
    }

    // 返回从 matrix[row][col] 出发的最长递增路径的长度
    private int dfs(int[][] matrix, int row, int col) {
        // 存储从 matrix[row][col] 出发的最长递增路径的长度，最少为 1
        int length = 1;
      
        // 遍历 matrix[row][col] 的相邻节点
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            int i = row + dir[0]; // 横坐标
            int j = col + dir[1]; // 纵坐标

            if (i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length && matrix[i][j] > matrix[row][col]) {
                // 从 matrix[i][j] 出发的最长递增路径的长度
                int path = dfs(matrix, i, j);
                // 从 matrix[row][col] 出发的最长递增路径的长度 = 从 matrix[i][j] 出发的最长递增路径的长度 + 1
                length = Math.max(path + 1, length);
            }
        }


        return length;
    }
}

但是如果使用上述的代码（也成为朴素深度优先搜索），时间复杂度是指数级，会超出时间限制，因此必须加以优化。

记忆化深度优先搜索

朴素深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。

由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用数组 memo 作为缓存矩阵，已经计算过的单元格的结果存储到缓存数组中。

使用记忆化深度优先搜索，当访问到一个单元格 (i,j)时，如果 memo[i][j] == 0 说明该单元格的结果已经计算过，则直接从缓存中读取结果，如果 memo[i][j] != 0，说明该单元格的结果尚未被计算过，则进行搜索，并将计算得到的结果存入缓存中。

遍历完矩阵中的所有单元格之后，即可得到矩阵中的最长递增路径的长度。

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        // 存储从 matrix[i][j] 出发的最长递增路径的长度
        int[][] memo = new int[matrix.length][matrix[0].length];

        // 存储最长递增路径的长度
        int res = 0;

        for (int i = 0; i < matrix.length; i ++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                int length = dfs(matrix, memo, i, j);
                res = Math.max(res, length);
            }
        }

        return res;
    }

    // 返回从 matrix[row][col] 出发的最长递增路径的长度
    private int dfs(int[][] matrix, int[][] memo, int row, int col) {
        // 如果 memo[i][j] > 0，就说明之前已经计算过从 matrix[row][col] 出发的最长递增路径的长度，直接返回
        if (memo[row][col] > 0) {
            return memo[row][col];
        }
      
        // 存储从 matrix[row][col] 出发的最长递增路径的长度，最少为 1
        int length = 1;
      
        // 遍历 matrix[row][col] 的相邻节点
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            int i = row + dir[0]; // 横坐标
            int j = col + dir[1]; // 纵坐标

            if (i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length && matrix[i][j] > matrix[row][col]) {
                // 从 matrix[i][j] 出发的最长递增路径的长度
                int path = dfs(matrix, memo, i, j);
                // 从 matrix[row][col] 出发的最长递增路径的长度 = 从 matrix[i][j] 出发的最长递增路径的长度 + 1
                length = Math.max(path + 1, length);
            }
        }

        // 更新 memo 数组
        memo[row][col] = length;

        return length;
    }
}

💥 复杂度分析