leetcode329. 矩阵中的最长递增路径_一个整数矩阵,输出最长严格的递增路径的长度。每个单元格,可以往上,下,左,右四个

传送门

题目: 给定一个整数矩阵，找出最长递增路径的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。
1
2
3
4
5
6

记忆化深度优先搜索

如果直接用DFS搜索，一定会超时，因为一条已经计算过的路径上的所有节点都要开始DFS一次。
所以,我们最好把之前搜索的结果缓存下来，
等我们要把当前节点加入到已有路径时，直接把记忆的路径长度+1（+1时加上当前节点）
这样每个子问题只需要计算一次。

缓存数组： dp[i][j] 代表以 i行j列的节点 为首或者尾的路径长度
1
2
3
4
5
6

在本问题中，我们多次递归调用 dfs(i,j) 。
但是，如果我们如果已经知道和matrix[i][j]相邻的四个单位置的结果(dp路径值)，
就只需要常数时间就可得到ij的dp值。 

所以 DFS里：
1. 先判断 ij上下左右四个位置索引是不是有效   
2. 再判断某个位置的值是不是比matrix[i][j]大，注意这里是大,不是小,因为路径端点比它大,它才能加入路径
1
2
3
4
5
6
7

	final int[][] dir = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int ans = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];// dp存路径长
        for (int i = 0; i < matrix.length; ++i) {
            for (int j = 0; j < matrix[0].length; ++j) {
                ans = Math.max(ans, DFS(matrix, dp, i, j));
            }
        }
        return ans;
    }

    int DFS(int[][] matrix, int[][] dp, int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];
        dp[i][j] = 1; // 这里要初始化 dp

        for (int k = 0; k < 4; ++k) {
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length ||
                matrix[i][j] >= matrix[x][y])
                continue;

            dp[i][j] = Math.max(dp[i][j], DFS(matrix, dp, x, y) + 1);
        }
        return dp[i][j];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28