House Robber

典型的动规问题，一开始设置了数组dp[len]，后来可以发现只跟2个数有关，可以用%来将空间复杂度降低到O(1) 根据答案进一步可以发现，其实当前值也无关，看第二个解法中，可以把curr理解成前一个值，而prev就是前前一个

class Solution {
    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i % 2] = Math.max(dp[(i-1) % 1], dp[(i-2) % 2] + nums[i]);
        }

        return dp[(nums.length - 1) % 2];
    }
}

public int rob(int[] num) {
    int prevMax = 0;
    int currMax = 0;
    for (int x : num) {
        int temp = currMax;
        currMax = Math.max(prevMax + x, currMax);
        prevMax = temp;
    }
    return currMax;
}

House Robber II

第一题的follow up，如果数组是一个环，头尾相接怎么办？ 遇到数组为环的时候，可以用拆环的办法 (另一种办法是double 利用已经做好的第一个题的办法，只要考虑边界情况

1. 选了第一个，不选最后一个
2. 选最后一个，不选第一个

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

    public int rob(int[] nums, int start, int end) {
        int prevMax = 0;
        int currMax = 0;
        for (int i = start; i <= end; i++) {
            int temp = currMax;
            currMax = Math.max(prevMax + nums[i], currMax);
            prevMax = temp;
        }
        return currMax;
    }
}

House Robber III

对于在树上，不能有相邻的节点

• 一个错误的理解是只要考虑隔层的情况，忽略了可能存在取第一层，第四层这样的。所以不能用bfs

最简单直接的想法是利用递归，rob(root)是取决于

1. rob(root.left), rob(root.right)
2. root + rob(root.left.left) .... + rob(root.right.right) (a.k.a root's grandchildren) 然而这个解法有了很多的重复计算，复杂度为O(n+n的左子树总数+n的右子树总数+

   The time complexity for the naive recursion in step I is indeed exponential. For each tree node tn at depth d, let T(d) be the number of times the rob function will be called on it. Then we have T(d) = T(d - 1) + T(d - 2). This is because rob will be called on tn either from its parent (at depth d - 1) or its grandparent (at depth d - 2), according to its definition. Note T(0) = T(1) = 1, i.e., rob will be called only once for the tree root and its two child nodes. Therefore T(d) will essentially be the (d+1)-th Fibonacci number (starting from 1), which grows exponentially (more info can be found here).

进而考虑到利用HashMap解决重复计算的问题，保存每个点已经计算过的值，确保每个点只用算一次O(n)

再进一步分析，发现主要需要考虑的是两种情况，root是否被rob，只需要保持这两个信息的可能传递下去。所以考虑建立一个返回值为int[]的helper，其中

1. int[0]为root没有被rob的情况，这只和root.left和root.right的int[]有关
2. int[1]为root被rob的情况，那么这就只和left[0]和right[0]有关

class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;

        int val = 0;

        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }

        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }

        return Math.max(root.val + val, rob(root.left) + rob(root.right));
    }
}

//HashMap, a naive DP solution
public int rob(TreeNode root) {
    return robSub(root, new HashMap<>());
}

private int robSub(TreeNode root, Map<TreeNode, Integer> map) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);

    int val = 0;

    if (root.left != null) {
        val += robSub(root.left.left, map) + robSub(root.left.right, map);
    }

    if (root.right != null) {
        val += robSub(root.right.left, map) + robSub(root.right.right, map);
    }

    val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));
    map.put(root, val);

    return val;
}

//
public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
    if (root == null) return new int[2];

    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    int[] res = new int[2];

    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];

    return res;
}