题目链接

LeetCode

题目描述

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

示例 3：

输入： matrix = [[1]]
输出： 1

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

  解题思路

  方法一：记忆化深度优先搜索

将矩阵看成一个有向图，每个单元格对应图中的一个节点，如果相邻的两个单元格的值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化成在有向图中寻找最长路径。

深度优先搜索是非常直观的方法。从一个单元格开始进行深度优先搜索，即可找到从该单元格开始的最长递增路径。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。

但是如果使用朴素深度优先搜索，时间复杂度是指数级，会超出时间限制，因此必须加以优化。

朴素深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵 memo 作为缓存矩阵，已经计算过的单元格的结果（从 i,j出发的最长递增路径大小）存储到缓存矩阵中。

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

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

相当于动态规划求memo

class Solution {
    private int rows, cols;
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0|| matrix[0].length == 0){
            return 0;
        }
        rows = matrix.length;
        cols = matrix[0].length;
        int longest = 0;
        int[][] remember = new int[rows][cols];
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                longest = Math.max(longest, dfs(matrix, i, j, remember));
            }
        }
        return longest;
    }
    private int dfs(int[][] matrix, int i, int j, int[][] memo){
        // 单元格被计算过，直接返回
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        // 加上当前单元格
        ++memo[i][j];
        // bfs搜索从当前单元格的长度 memo[i][j]
        // 如果左边单元格大于当前单元格 向上搜索
        if(i > 0 && matrix[i - 1][j] > matrix[i][j]){
            // 1 + dfs(matrix, i - 1, j, memo) 表示 当前单元格 1 加上 memo[i-1][j] 的长度
            memo[i][j] = Math.max(memo[i][j], 1 + dfs(matrix, i - 1, j, memo));
        }
        // 如果下面单元格大于当前单元格 向下搜索
        if(j + 1 < cols && matrix[i][j + 1] > matrix[i][j]){
            memo[i][j] = Math.max(memo[i][j], 1 + dfs(matrix, i, j + 1, memo));
        }
        // 如果右边单元格大于当前单元格 向右搜索
        if(i + 1 < rows && matrix[i + 1][j] > matrix[i][j]){
            memo[i][j] = Math.max(memo[i][j], 1 +  dfs(matrix, i + 1, j, memo));
        }
        // 如果上面单元格大于当前单元格 向上搜索
        if(j > 0 && matrix[i][j - 1] > matrix[i][j]){
            memo[i][j] = Math.max(memo[i][j], 1 +  dfs(matrix, i, j - 1, memo));
        }
        return memo[i][j];
    }
}

• 时间复杂度 O(nm)
• 空间复杂度 O(nm)