BM61 题解 | #矩阵最长递增路径#

阿哈时刻：

整体的思路，就是

1、用一个dp[i][j]二维数组来记录，当前这个格子能走多少步！

2、那怎么知道能走多少步呢，一个格子算一步，所有能走多少步dp[i][j] = 自己 + 四个方向能走的最大步数，也就是：

dp[i][j] = Math.max(dp[i][j], dp[nexti][nextj]+1); //这个是我通过思路，理解出来的！！！

看matrix的值，就知道了

比如，matrix是：
[
 [1,2,3],
 [4,5,6],
 [7,8,9]
 ]
那么，dp的值是 ：
[
 [5,4,3],
 [4,3,2],
 [3,2,1]
 ]

3、最后，在遍历maxtrix的过程中顺便，记录dp[i][j]的最大值进行返回，就是目标值了。

import java.util.*;


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

    public int dfs(int[][] matrix, int[][] dp, int i, int j) {
        if(dp[i][j] != 0) {
            return dp[i][j];
        }
        dp[i][j]++; //一个格子算一步，如果没有走到这里就先赋值一步，再不断遍历
        for(int k=0; k<4; k++) {
            int nexti = i + dirs[k][0];
            int nextj = j + dirs[k][1];
            if(nexti>=0 && nexti <n && nextj>=0 && nextj< m && matrix[nexti][nextj] > matrix[i][j] ) {
                dp[i][j] = Math.max(dp[i][j], dfs(matrix, dp, nexti, nextj)+1);
            }
        }
        return dp[i][j];
    }

    /**
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0) {
            return 0;
        }
        n = matrix.length;
        m = matrix[0].length;
        int[][] dp = new int[n][m];
        int maxLen = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++){
                maxLen = Math.max(maxLen, dfs(matrix, dp, i, j));
            }
        }
        String dps = Arrays.deepToString(dp);
        return maxLen;
    }



}