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

带缓存的dfs

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
        if (matrix == null || matrix.length  == 0) {
            return 0;
        }
        int max = 0;
        int N = matrix.length, M = matrix[0].length;
        int[][] cache = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                max = Math.max(max, maxLength(matrix, i, j, -1, cache, N, M));
            }
        }
        return max;
    }
    int[][] directions = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int maxLength(int[][] matrix, int i, int j, int pre, int[][] cache, int N, int M) {
        if (i < 0 || i == N || j < 0 || j == M || matrix[i][j] <= pre) {
            return 0;
        }
        int max = cache[i][j];
        if (max == 0) {
            for (int[] direction : directions) {
                int len = maxLength(matrix, i + direction[0], j + direction[1], matrix[i][j], cache, N, M);
                max = Math.max(max, len + 1);
            }
            cache[i][j] = max;
        }
        return max;
    }
}