Java Solution, DFS + memorization

• ``````public class Solution{
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rowLen = matrix.length;
int colLen = matrix[0].length;
int[][] dis = new int[rowLen][colLen]; // to store the longest increasing length from current point
int res = 0;

for(int i = 0; i < rowLen; i++)
{
for(int j = 0; j < colLen; j++)
{
res = Math.max(res, dfs(dis, rowLen, colLen, i, j, matrix));
}
}

return res;
}

public int dfs(int[][] dis, int rowLen, int colLen, int x, int y, int[][] matrix) {
if(dis[x][y] != 0)
return dis[x][y];

for(int i = 0; i < 4; i++)
{
int newX = x + dx[i];
int newY = y + dy[i];

if(newX >= 0 && newY >= 0 && newX < rowLen && newY < colLen && matrix[x][y] < matrix[newX][newY])
{
dis[x][y] = Math.max(dis[x][y], dfs(dis, rowLen, colLen, newX, newY, matrix));
}
}

dis[x][y]++;
return dis[x][y];
}``````

• if all all the element in the martix is same,this solution will return 1。 is this correct?

• do you really need to check visited ? it wont be circle because the value is keep increasing and it never come back to the patch that you visited.

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