Easy understanding java method using DP from up to down


  • 0
    public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int[][] memo = new int[matrix.length][matrix[0].length];
        for(int i = 0 ; i < matrix.length ; i++) {
            for(int j = 0 ; j < matrix[0].length ; j++) {
                max = Math.max(max , dfs(matrix , i , j , memo));
            }
        }
        return max;
    }
    
    protected int dfs(int[][] matrix , int x , int y , int[][] memo) {
        if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {
            return 0;
        }
        if(memo[x][y] != 0) {
            return memo[x][y];
        }
        int left = 0 ,up = 0 , right = 0 , down = 0;
        if(y-1 >= 0 && matrix[x][y-1] > matrix[x][y])  {
            left = dfs(matrix , x , y-1 , memo);
        }
        if(x-1 >= 0 && matrix[x-1][y] > matrix[x][y]) {
            up = dfs(matrix , x-1 , y , memo);
        }
        if(y+1 < matrix[0].length && matrix[x][y+1] > matrix[x][y]) {
            right = dfs(matrix , x , y+1 , memo);
        }
        if(x+1 < matrix.length && matrix[x+1][y] > matrix[x][y]) {
            down = dfs(matrix , x+1 , y , memo);
        }
        int max1 = Math.max(left , right);
        int max2 = Math.max(up , down);
        int max = Math.max(max1 , max2) + 1;
        memo[x][y] = max;
        return max;
    }
    

    }


Log in to reply
 

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