# Clean Java DFS & DP solution

• ``````public class Solution {
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0)  return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int max = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++){
int tmp = longestIncreasingPathDFS(matrix, i, j, m, n, dp);
if(tmp > max)   max = tmp;
}
return max;
}
private int longestIncreasingPathDFS(int[][] matrix, int i, int j, int m, int n, int[][] dp){
if(dp[i][j] != 0)   return dp[i][j];
int max = 1;
if(i > 0 && matrix[i][j] < matrix[i-1][j]){      //can go left
max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i-1, j, m, n, dp));
}
if(i < m-1 && matrix[i][j] < matrix[i+1][j]){      //can go right
max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i+1, j, m, n, dp));
}
if(j > 0 && matrix[i][j] < matrix[i][j-1]){      //can go up
max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i, j-1, m, n, dp));
}
if(j < n-1 && matrix[i][j] < matrix[i][j+1]){      //can go down
max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i, j+1, m, n, dp));
}
dp[i][j] = max;
return max;
}
}``````

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