Memorized Search:

记忆化搜索本质上和DP是一样的记录已经计算过的子问题，不做重复计算。

初始化状态找不到，状态转移不确定的时候尤其好用。相当于dfs+剪枝

Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

思路：

dp[x][y] = Math {dp[nx][ny] + 1} nx,ny 上下左右

public class Solution {
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    int[][] dp;
    int[][] visited;
    int n;
    int m;
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // Write your code here
        if (A == null || A.length == 0)
            return 0;
        m = A.length;
        n = A[0].length;

        int res = 0;
        dp = new int[m][n];
        visited = new int[m][n];

        for (int[] a : dp) {
            Arrays.fill(a, 1);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // loop over each point in matrix
                dp[i][j] = dfs(i, j, A);
                res = Math.max(dp[i][j], res);
            }
        }

        return res;
    }

    public int dfs(int x, int y, int[][] A) {
        // pruning 
        if (visited[x][y] == 1) {
            return dp[x][y];
        }

        int ans = dp[x][y]; 
        int nx , ny;

        // 4 possibe previous number 
        for(int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(0 <= nx && nx < m && 0<= ny && ny < n ) {
                if( A[x][y] < A[nx][ny]) {
                    ans = Math.max(ans,  dfs( nx, ny, A) + 1);
                }
            }
        }
        visited[x][y] = 1;
        dp[x][y] = ans;
        return ans;

    }
}