每日一题：矩阵中最长递增路径（记忆化搜索）

题意

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

Solution

记忆化搜索模板题。$dp[i][j]$记录之前已经计算得到的结果，之后直接读取即可。

Code

class Solution329 {
    /*
           [7,8,9]
           [9,7,6]
           [7,2,3]
           输出：6
         */

    public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int n, m;

    public int dfs(int[][] a, int[][] dp, int x, int y) {
        if(dp[x][y] != 0)
            return dp[x][y];
        dp[x][y] = 1;
        for(int[] dir : dirs) {
            int fx = x + dir[0], fy = y + dir[1];
            if(fx >= 0 && fx < n && fy >= 0 && fy < m && a[fx][fy] > a[x][y])
                dp[x][y] = Math.max(dp[x][y], dfs(a, dp, fx, fy) + 1);
        }
        return dp[x][y];
    }

    public int longestIncreasingPath(int[][] a) {
        n = a.length;
        if(n == 0)
            return 0;
        m = a[0].length;
        int res = 1;
        int[][] dp = new int[n][m];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                res = Math.max(res, dfs(a, dp, i, j));
            }
        }
        return res;
    }
}