JAVA DP+DFS simple solution and explanation


  • 0
    A
    public static int longestIncreasingPath(int[][] matrix){
    	int m=matrix.length;
    	if(m==0) return 0;
    	int n=matrix[0].length;
    	if(n==0) return 0;
    
    	int longest=0;
    	int[][] dp=new int[m][n];
    	boolean[][] visited=new boolean[m][n];
    
    	for(int i=0; i<m; i++){
    		for(int j=0; j<n; j++){
    			int curr_length=dfs(matrix,dp,visited,i,j);
    			longest=Math.max(longest,curr_length);
    		}
    	}
    	return longest;
    }
    
    private static int dfs(int[][] matrix, int[][] dp, boolean[][] visited, int i, int j){	
    	int m=matrix.length;
    	int n=matrix[0].length;
    	if(!visited[i][j]){
    		int[] directions={0,-1,0,1,0};
    		visited[i][j]=true;
    		int current_max=0;
    		for(int d=0; d<4; d++){
    			int next_row=i+directions[d];
    			int next_col=j+directions[d+1];
    			if(next_row>=0 && next_row<m &&
    				next_col>=0 && next_col<n &&
    				matrix[i][j]<matrix[next_row][next_col]){
    				int curr=dfs(matrix,dp,visited,next_row,next_col);
    				current_max=Math.max(current_max,curr);
    			}
    		}
    		dp[i][j]=current_max+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.