My Java accepted solution. Dynamic Programming method.


  • 0
    Z
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0) return 0;
            int[][] A = new int[matrix.length][matrix[0].length];
            int res = 0;
            for(int i=0;i<matrix.length;i++) {
                for(int j=0;j<matrix[0].length;j++) {
                    res = Math.max(helper(matrix,A,i,j) ,res) ;
                }
            }
            
            return res;
        }
        
        public int helper(int[][] matrix,int[][] A, int i, int j) {
            if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
                return 0;
            }
            // if A[i][j] is visited then return
            if(A[i][j] != 0) return A[i][j];
            A[i][j] = 1;
            if(i > 0 && matrix[i][j] < matrix[i-1][j]) {
                A[i][j] = Math.max(A[i][j] ,1 + helper(matrix,A,i-1,j) );
            }
            if(j > 0 && matrix[i][j] < matrix[i][j-1]) {
                A[i][j] = Math.max(A[i][j],1 + helper(matrix,A,i,j-1));
            }
            if(i < matrix.length -1 && matrix[i][j] < matrix[i+1][j]) {
                A[i][j] = Math.max(A[i][j],1 + helper(matrix,A,i+1,j));
            }
            if(j < matrix[0].length -1 && matrix[i][j] < matrix[i][j+1]) {
                A[i][j] = Math.max(A[i][j],1 + helper(matrix,A,i,j+1));
            }
            return A[i][j];
        }
    }

  • 0
    D

    Why your helper method looks like a DFS to me? Can you please help me understand? Thx~


Log in to reply
 

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