Java dfs+dp solution


  • 0
    M

    time: O(mn)
    space: O(mn)

    public class Solution {
        int M, N;
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix==null || matrix.length==0) return 0;
            M = matrix.length; N = matrix[0].length;
            int max = 0;
            int[][] dp = new int[M][N];
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    max = Math.max(max, dfs(i, j, matrix, dp));
                }
            }
            return max;
        }
        
        private int dfs(int i, int j, int[][] matrix, int[][] dp){
            if(dp[i][j]!=0) return dp[i][j];
            int len = 1;
            if(i-1>=0 && matrix[i-1][j]>matrix[i][j]){
                len = dfs(i-1, j, matrix, dp)+1;
            }
            if(i+1<M && matrix[i+1][j]>matrix[i][j]){
                len = Math.max(len, dfs(i+1, j, matrix, dp)+1);
            }
            if(j-1>=0 && matrix[i][j-1]>matrix[i][j]){
                len = Math.max(len, dfs(i, j-1, matrix, dp)+1);
            }
            if(j+1<N && matrix[i][j+1]>matrix[i][j]){
                len = Math.max(len, dfs(i, j+1, matrix, dp)+1);
            }
            dp[i][j] = len;
            return len;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.