Longest increasing path in a matrix - Teeeeeebag/LeetCode GitHub Wiki

1. Memorized DFS

public class Solution {
    private int getDepth(int[][] matrix, int x, int y, int[][] cnt){
        if (cnt[x][y] != 0){ 
            return cnt[x][y];
        }   
        int crtCnt = 1;
        if (x-1>=0 && matrix[x][y] > matrix[x-1][y]){
            crtCnt = Math.max(getDepth(matrix, x-1, y, cnt)+1, crtCnt);
        }   
        if (x+1 < matrix.length && matrix[x][y] > matrix[x+1][y]){
            crtCnt = Math.max(getDepth(matrix, x+1, y, cnt)+1, crtCnt);
        }   
        if (y-1>=0 && matrix[x][y] > matrix[x][y-1]){
            crtCnt = Math.max(getDepth(matrix, x, y-1, cnt)+1, crtCnt);
        }   
        if (y+1 < matrix[0].length && matrix[x][y] > matrix[x][y+1]){
            crtCnt = Math.max(getDepth(matrix, x, y+1, cnt)+1, crtCnt);
        }   
        cnt[x][y] = crtCnt;
        return crtCnt;
    }   
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int[][] cnt = new int[matrix.length][matrix[0].length];
        int maxLen = 1;
        for (int i=0; i<matrix.length; ++i){
            for (int j=0; j<matrix[0].length; ++j){
                maxLen = Math.max(maxLen, getDepth(matrix, i, j, cnt));
            }   
        }   
        return maxLen;
    }   
}