198. 打家劫舍

dp数组表示第i个位置处能取得的最大金额（取该位置偷nums[k-1] + dp[k-2]和不偷dp[k-1]的最大值）
因为状态转移方程中，dp[i]涉及到dp[i-2], 在base case 中，在最前面加一个虚拟的空房子，状态更容易转换。而dp[1] 就初始化为nums[0]

def rob(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0

    # 子问题：
    # f(k) = 偷 [0..k) 房间中的最大金额

    # f(0) = 0
    # f(1) = nums[0]
    # f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    N = len(nums)
    dp = [0] * (N+1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N+1):
        dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
    return dp[N]

213. 打家劫舍 II

现在房子环成了一个圈，也就是说第一间和最后一间不能同时抢。那么有：
1. 抢第一间，不抢最后一间
2. 不抢第一间，抢最后一间
3. 不抢第一间，不抢最后一间
  
  实际上，情况3的结果是小于情况2的（或者可以说是包含关系）, 所以我们只需要考虑情况1,2。
因此，当有多于1个房子时，只需要比较nums[:-1] , nums[1:] 并返回最大值max(my_rob(nums[:-1]),my_rob(nums[1:]))即可

class Solution(object):
    def rob(self,nums):
        def my_rob(nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 0:
                return 0
            dp=[0]*(len(nums)+1)
            dp[0]=0
            dp[1]=nums[0]
            for i in range(2,len(nums)+1):
                dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
            return dp[-1]
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0] # 可能只有一个房子

class Solution {
public:
    int helper(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 0);
        dp[1] = nums[0];
        for (int i = 2; i < nums.size() + 1; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp.back();
    }

    int rob(vector<int> &nums) {
        if (nums.size() == 1) return nums[0];
        vector<int> n1(nums.begin(), nums.end() - 1);
        vector<int> n2(nums.begin() + 1, nums.end());
        return max(helper(n1), helper(n2));
    }
};

337 树形打家劫舍

对于每一个节点，都只有选和不选两种情况。数组中[ , ]第一个index表示不打劫当前节点的收益，第二个index表示打劫当前节点的收益
如果没选当前节点，则可以选左右节点（withoutRoot=max(l)+max(r)）。如果选了当前节点，则不能选左右节点（withRoot=root.val+l[0]+r[0]）
递归函数返回以当前节点为根时[不打劫当前节点，打劫当前节点]时的状态.递归函数中，相当于进行了后序遍历：先求左右子树对应的结果，再根据这个结果和当前节点进行组合，得到当前节点的结果
递归函数结束的条件：当前节点为空

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def rob(self, root):
        def dp(root):
            if not root: return [0,0] # 不偷/偷的收益. 递归结束的条件
            l=dp(root.left) # 左节点不偷/偷带来的收益  # 后序遍历：左
            r=dp(root.right)# 右节点不偷/偷带来的收益  # 后序遍历：右
            # 后序遍历：中
            # 若偷当前节点，则收益=当前节点+左节点不偷+右节点不偷
            # 若不偷当前节点，则收益=左节点偷或不偷的最大值+右节点偷或不偷的最大值
            withRoot=root.val+l[0]+r[0] # 若偷当前节点
            withoutRoot=max(l)+max(r) # 若不偷当前节点
            return [withoutRoot,withRoot]

        return max(dp(root)) # 返回 不偷/偷当前节点 的收益最大值

class Solution {
public:
    vector<int> helper(TreeNode *root) {
//        当前节点为空时，返回收益
        if (root== nullptr ) {
            return {0, 0};
        }
        vector<int> l = helper(root->left); 
        vector<int> r = helper(root->right);
        int withRoot=root->val+l[0]+r[0];
        int withoutRoot=*max_element(l.begin(), l.end())+*max_element(r.begin(), r.end());
        return {withoutRoot,withRoot};
    }
    int rob(TreeNode *root) {
        vector<int> res=helper(root);
        return *max_element(res.begin(),res.end());
    }
};