16ms JAVA dfs + memorization


  • -1
    A
    public class Solution {
    int max = 1;
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
          return 0;
         int[][] dp = new int[matrix.length][matrix[0].length];
         for(int[] arr: dp)
            Arrays.fill(arr, 0);
         for(int i = 0; i < matrix.length; i++) {
             for(int j = 0; j < matrix[0].length; j++)
               helper(matrix, i, j, dp);
         }
         return max;
    }
    
    public int helper(int[][] matrix, int i, int j, int[][] dp) {
        if(dp[i][j] != 0)
          return dp[i][j];
          
        int res = 0;
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        for(int t = 0; t < 4; t++) {
            int x = i + dx[t];
            int y = j + dy[t];
            if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j])
              continue;
            res = Math.max(res, helper(matrix, x, y, dp));
        }
        
        dp[i][j] = res + 1;
        max = Math.max(max, dp[i][j]);
        return dp[i][j];
        
    }
    

    }


Log in to reply
 

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