Detailed explanation and 15ms JAVA solution

• 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];
}``````

• Very detailed explanation.

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