打家劫舍问题

参考：打家劫舍问题 leetcode题解

用递归先实现：自下而上实现（超时

class Solution {
    int[] memory;
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        memory = new int[nums.length];
        return helper(nums,0);
    }
    public int helper(int[] nums, int index){
        if(index >= nums.length){
            return 0;
        }
        if(memory[index] != 0) return memory[index];
        int res = 0;
        for(int i = index; i<nums.length; i++){
            res = Math.max(res,nums[i]+helper(nums,i+2));
            memory[index] = res;
        }
        return res;
    }
}

证明我这个递归存在问题。参考了题解得到下面这种递归（AC：

class Solution {
    private int[] memo;
	public int rob(int[] nums) {
	    // 初始化备忘录
	    memo = new int[nums.length];
	    Arrays.fill(memo, -1);
	    // 强盗从第 0 间房子开始抢劫
	    return dp(nums, 0);
	}

// 返回 dp[start..] 能抢到的最大值
	private int dp(int[] nums, int start) {
	    if (start >= nums.length)
	        return 0;
	    // 避免重复计算
	    if (memo[start] != -1) return memo[start];
	    int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));
	    // 记入备忘录
	    memo[start] = res;
	    return res;
	 }
}

所有的状态都归结于抢与不抢这两种情况，取最大值。不抢 dp(nums, start + 1)，抢的话 nums[start] + dp(nums, start + 2)

最后回到了我们的动态规划（自顶向下：

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        int[] dp = new int[len+2];
        for(int i = len-1; i>=0; i--){
            dp[i] = Math.max(dp[i+1],dp[i+2]+nums[i]);
        }
        return dp[0];
    }
}

---

这无非是在打家劫舍1的情况下多出了两种情况，问题变成了从0到n-2和1到n-1这两种情况的最大值：

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        int[] dp = new int[len+2];
        for(int i = len-2; i>=0; i--){
            dp[i] = Math.max(dp[i+1],dp[i+2]+nums[i]);
        }
        for(int i = len-1; i>=1; i--){
            dp[i] = Math.max(dp[i+1],dp[i+2]+nums[i]);
        }
        return Math.max(dp[0],dp[1]);
    }
}

---

根据上面的规则，无非是两种情况，打劫or不打劫：

class Solution {
    HashMap<TreeNode,Integer> map = new HashMap<>();  //记忆化
    public int rob(TreeNode root) {
        if(root == null) return 0;
        if(map.containsKey(root)) return map.get(root);
        int do_it = root.val + (root.left == null ? 0:rob(root.left.left)+rob(root.left.right)) // 打劫
        + (root.right == null ? 0:rob(root.right.left) + rob(root.right.right));
        int not_do = rob(root.left) + rob(root.right); // 不打劫
        int maxs = Math.max(do_it,not_do);  // 求这两种情况的最大值
        map.put(root,maxs);
        return maxs;
    }
}