Detailed explanation and 15ms JAVA solution


  • 0
    B

    We use dp[row][column] to store the longest path, from any possible cell, to matrix[row][column].

    For example

    Matrix:

    [9,9,4]

    [6,6,8]

    [2,1,1]

    dp:
    [0,0,0]

    [0,0,0]

    [0,0,0]

    We first find out what dp[0][0] is. That is, we want to know what the longest increasing path to Matrix[0][0] is. Due to our recursive structure, we have to find the longest path to its surrounding (only up, down, left and right) cells which have a smaller value. So we can add one to the largest of those to know the longest path to Matrix[0][0].

    Thus, we need to know dp[1][0].
    To know dp[1][0], we need to know dp[2,0].
    To know dp[2][0], we have to know dp[2,1].
    Since there are no adjacent cells that have a smaller value than Matrix[2][1], dp[2][1] = 1 and dp[2][1] is the starting point of a path.

    At the time we know dp[0][0], we not only know dp[0][0], but a bunch of others, from which we get the value of dp[0][0].
    Before we try to figure out the value of dp[0,1], the dp looks like:

    dp:
    [4,0,0]

    [3,0,0]

    [2,1,0]

    A lot of values are known. For known values, we don’t have to calculate them again.

    At the time we know dp[0,1], the dp looks like:

    dp:

    [4,3,0]

    [3,2,0]

    [2,1,0]

    At the time we know dp[0,2], the dp looks like:

    dp:

    [4,3,1]

    [3,2,0]

    [2,1,0]

    Then, we can skip dp[1][0], dp[1][1].
    By the time we know dp[1,2], dp looks like:

    dp:

    [4,3,1]

    [3,2,3]

    [2,1,1]

    The largest number in dp is the answer.
    Below is my code. Thank you for reading.

    static final int[][] suround = {{1,0},{0,1},{-1,0},{0,-1}};
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0){
            return 0;
        }
    	int longest = 0;
    	int rowNum = matrix.length;
    	int colmnNum = matrix[0].length;
    	int[][] dp = new int[rowNum][colmnNum];
    	for(int row = 0; row < rowNum; row ++){
    		for(int column = 0; column < colmnNum; column ++){
    			longest = Math.max(longest, longestIncreasingPathHelper(matrix,row,column,dp));
    		}
    	}
    	return longest;
    }
    public int longestIncreasingPathHelper(int[][] matrix, int row, int column, int[][] dp) {
    	if(dp[row][column] != 0){
    		return dp[row][column];
    	}
    	int mx = 0;
    	
    	for(int i = 0; i < 4;i++){
    		
    		int nextRow = row + suround[i][0];
    		int nextColumn = column + suround[i][1];
    		
    		if(nextRow>= 0 && nextRow < matrix.length && nextColumn >= 0 && nextColumn < matrix[0].length
    				&& matrix[nextRow][nextColumn] < matrix[row][column]
    				){
    			
    			mx = Math.max(mx, longestIncreasingPathHelper(matrix, nextRow, nextColumn,dp));
    		}
    	}
    	dp[row][column] = mx + 1;
    	return dp[row][column];
    }

  • 0
    N

    Very detailed explanation.


Log in to reply
 

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