This is the 2d version LIS problem, thinking it from the reverse direction is easier for me. I used a m*n array to save the middle result. `dp[x][y] = Math.max(dp[x][y], search(matrix, dp, nx, ny) + 1);`

is the core code to realize the search, basically we either inherit the previous search result or add one to the recursive call. Hope it helps and any suggestion to improve it is welcome!

Edit: Modify the logic a bit to make it clearer. This is very nice problem, worth thinking through. The method can be easily extended a few other problems.

```
int m, n;
int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].length) == 0) {
return 0;
}
int best = 0;
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
best = Math.max(best, helper(matrix, dp, i, j));
}
}
return best;
}
private int helper(int[][] matrix, int[][] dp, int i, int j) {
if(dp[i][j] > 0) {
return dp[i][j];
}
dp[i][j] = 1;
for(int[] d : direction) {
int x = i + d[0];
int y = j + d[1];
if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
int dis = helper(matrix, dp, x, y) + 1;
dp[i][j] = Math.max(dp[i][j], dis);
}
}
return dp[i][j];
}
```