14ms java solution, easy to understand


  • 0
    • Find longest decreasing path starting from each matrix[i][j] and store the result in the corresponding dp[i][j] so we don't need to calculate again

    • The answer is the max value in the matrix dp[n][m]

    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            int n = matrix.length;
            if(n==0) return 0;
            int m = matrix[0].length;
            int[][] dp = new int[n][m];
            int res = 0;
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    res = Math.max(res,helper(matrix,i,j,dp,Integer.MAX_VALUE));
                }
            }
            return res;
        }
        
        public int helper(int[][] matrix, int i, int j, int[][] dp, int num){
            if(i<0||i>=matrix.length||j<0||j>=matrix[0].length||matrix[i][j]>=num) return 0;
            if(dp[i][j]>0) return dp[i][j];
            int cur = matrix[i][j];
            int v1 = helper(matrix,i+1,j,dp,cur);
            int v2 = helper(matrix,i-1,j,dp,cur);
            int v3 = helper(matrix,i,j+1,dp,cur);
            int v4 = helper(matrix,i,j-1,dp,cur);
            dp[i][j] = Math.max(Math.max(v1,v2),Math.max(v3,v4))+1;
            return dp[i][j];
        }
    }
    

Log in to reply
 

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