Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return4
The longest increasing path is[1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return4
The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

Solution: dp + memorized search. dp[i][j] > 0时说明已搜索过

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    public int longestIncreasingPath(int[][] A) {
        if(A == null || A.length == 0 || A[0] == null || A[0].length == 0){
            return 0;
        }
        int m = A.length, n = A[0].length, ans = 1;
        int[][] dp = new int[m][n];        

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = search(A, dp, i, j);
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
    private int search(int[][] matrix, int[][] dp, int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        dp[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= matrix.length || ny < 0 || ny >= matrix[0].length) {
                continue;
            }
            if (matrix[x][y] > matrix[nx][ny]) {
                dp[x][y] = Math.max(dp[x][y], search(matrix, dp, nx, ny) + 1);
            }
        }
        return dp[x][y];
    }