LongestIncreasingPath.java

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int rowN = matrix.length, colN = matrix[0].length;
        int res = 0;
        int[][] cache = new int[rowN][colN];
        for  (int i=0; i<rowN; i++) {
            for  (int j=0; j<colN; j++) {
                res = Math.max(res, findMax(matrix, i, j, cache)+1);
            }
        }
        return res;
    }

    int findMax(int[][] A, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) return cache[i][j];
        int rowN = A.length, colN = A[0].length;
        if (i>0 && i < rowN && A[i][j] < A[i-1][j]) // top
            cache[i][j] = findMax(A, i-1, j, cache)+1;
        if (i < rowN-1 && A[i][j] < A[i+1][j]) // bottom
            cache[i][j] = Math.max(cache[i][j], findMax(A, i+1, j, cache)+1);
        if (j>0 && j < colN && A[i][j] < A[i][j-1]) // left
            cache[i][j] = Math.max(cache[i][j], findMax(A, i, j-1, cache)+1);
        if (j < colN-1 && A[i][j] < A[i][j+1]) // right
            cache[i][j] = Math.max(cache[i][j], findMax(A, i, j+1, cache)+1);
        return cache[i][j];
    }
}