# java dfs + memo, 13 ms beats 97%

• Basically 2 steps to solve this problem:
1.start from path[i][j] == 0, which means we haven't visited this point before.
2.The reason I designed this being DFS is that we need to get the total length starting from where we begin. Here we can use a memo.

``````public class Solution {
public static final int[] delta = new int[]{0,1,0,-1,0};
public int longestIncreasingPath(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int max = 0;
int[][] path = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(path[i][j] == 0) {
max = Math.max(max, walk(path, i, j, matrix));
}
}
}
return max;
}

private int walk(int[][] path, int i, int j, int[][] matrix) {
if(path[i][j] != 0) return path[i][j];
int value = 1;
for(int d = 1; d < delta.length; d++) {
int newI = i + delta[d];
int newJ = j + delta[d-1];
if(newI >= 0 && newI < path.length && newJ >= 0 && newJ < path[0].length
&& matrix[newI][newJ] > matrix[i][j]) {
value = Math.max(value, walk(path, newI, newJ, matrix) + 1);
}
}
path[i][j] = value;
return value;
}
}``````

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