Memorization

• 初始狀態不容易找到

• 狀態轉移沒有順序性

337. House Robber III

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]

return 3+3+1=7

• Use a map to do memorization in recursion

private Map<TreeNode, Integer> map = null;
public int rob(TreeNode root) {
    map = new HashMap<>();
    return helper(root);
}

private int helper(TreeNode node){
    if(node == null) return 0;

    if(map.containsKey(node)) return map.get(node);

    int val = node.val;

    if(node.left != null) val+=(helper(node.left.left)+helper(node.left.right));
    if(node.right != null) val+=(helper(node.right.left)+helper(node.right.right));

    int ans = Math.max(val, helper(node.left)+helper(node.right));
    map.put(node, ans);

    return ans;
}

Longest Continuous Increasing Subsequence 2D

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

• State: dp[i][j]: 以A[i][j]為出發點LCIS

public class LCIS2D {
    int[][] dp = null;

    private int LCIS(int[][] A){
        int max = 1;
        int m = A.length;
        int n = A[0].length;

        dp = new int[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                max = Math.max(max, dfs(A, i, j));
            }
        }
        return max;
    }

    private int dfs(int[][] A, int x, int y){
        if(dp[x][y] != 0) return dp[x][y];

        int m = A.length;
        int n = A[0].length;
        int ans = 1;

        int[] dx = new int[]{0, 0, 1, -1};
        int[] dy = new int[]{1, -1, 0, 0};

        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n){
                if(A[nx][ny] > A[x][y]){
                    ans = Math.max(ans, dfs(A, nx, ny)+1);
                }
            }
        }
        dp[x][y] = ans;
        return ans;
    }
    public static void main(String[] args) {
        LCIS2D l1 = new LCIS2D();
        int[][] tmp = new int[][]{
                {1, 6, 7, 9},
                {8, 9, 6, 3},
                {5, 1, 9, 8},
                {6, 5, 6, 7}   // 1->5->6->7->8->9
        };
        System.out.println(l1.LCIS(tmp));
    }
}