题解 | 矩阵最长递增路径

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
     int m = 0;
    int n = 0;
    int maxDistance = 0;
    int[][] memo; // 使用记忆化搜索 记录下之前的结果
    public int solve (int[][] matrix) {
        // write code here
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                //遍历每个点 看看能走到的最长路径
                int distance = dfs(i, j, matrix);
                
                maxDistance = Math.max(maxDistance, distance);
            }
        }
        System.out.println(Arrays.deepToString(memo));
        return maxDistance;

    }

    private int dfs(int i, int j, int[][] matrix) {

        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        int distance = 1;
        int up = 0;
        int down = 0;
        int left = 0;
        int right = 0;
        if (i + 1 < m && matrix[i][j] < matrix[i+1][j] ) {
            down =  dfs(i+1, j, matrix);
        }
        if (i - 1 >= 0 && matrix[i][j] < matrix[i-1][j] ) {
            up = dfs(i-1, j, matrix);
        }
        if (j + 1 < n && matrix[i][j] < matrix[i][j+1]) {
            right = dfs(i, j+1, matrix);
        }
        if (j - 1 >= 0 && matrix[i][j] < matrix[i][j-1] ) {
            left = dfs(i, j-1, matrix);
        }
        int res = distance + Math.max(up, Math.max(down, Math.max(left, right)));
        memo[i][j] = res;

        return res;

    }
}