day39

打家劫舍三道题：
街道题递推公式：dp[i] = max(dp[i-2] + nums[i], dp[i-1])（当前这户偷还是不偷）；
围城题就要分两种情况去考虑，分别是不含首元素，和不含尾元素，其它和前面一致；

二叉树题比较难，如下：
vector<int> traversal(TreeNode* cur){
        vector<int> dp(2, 0);
        //递归出口
        if(cur == nullptr) return {0, 0};
        //左
        vector<int> leftdp = traversal(cur->left);
        //右
        vector<int> rightdp = traversal(cur->right);
        //中
        //不偷当前结点，那么就要考虑偷左右孩子结点（不是一定偷，主要是取最大值）
        int val1 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);
        //偷当前结点，那么左右孩子结点一定不能偷了
        int val2 = cur->val + leftdp[0] + rightdp[0];

        return {val1, val2};
    }
    int rob(TreeNode* root) {
        //打家劫舍二叉树
        //递归采用后序遍历的方式，因为决定偷不偷当前结点是由左右子节点偷不偷决定的
        //定义一个包含两个元素的一维dp数组(每层递归里都有个dp数组)
        //dp[0]表示不偷当前结点盗取的最大金额，dp[1]表示偷当前结点盗取的最大金额
        //递归函数最后返回的也是一个dp数组，表示偷不偷根节点（所有子节点都遍历完了）
        vector<int> result = traversal(root);
        return max(result[0], result[1]);
    }