class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1){
            return nums[0];
        }
        vector<int> dp1(n-1);
        dp1[0] = nums[0];
        if(n <=2){
            return max(nums[0], nums[1]);
        }
        if(n <= 3){
            return max(nums[0], max(nums[1], nums[2]));
        }
        dp1[1] = max(nums[0], nums[1]);
        vector<int> dp2(n-1);
        dp2[0] = nums[1];
        dp2[1] = max(nums[1], nums[2]);
        for(int i=2; i<n-1; i++){
            dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]);
        }
        for(int i=3; i<n; i++){
            dp2[i-1] = max(dp2[i-2], dp2[i-3] + nums[i]);
        }
        return max(dp1[n-2], dp2[n-2]);
    }
};

337.打家劫舍III

这个打家劫舍的题也是二周目了，上一周目印象很深，所以本来以为能写对的，但还是在dp数组上面写错了。问题就出在了第二个向量，也就是不打劫根节点的时候的更新方式上面：

我写的更新代码如下：
int second = max(right[0] + left[0], right[1] + left[1]);

但实际正确的应该是：
int second = max(left[0], left[1]) + max(right[0], right[1]);

这两句之间差在哪了呢？差就差在，上面这个写法，左子树和右子树只能同时选择偷这个节点或不偷这个节点，但实际这个逻辑是不对的，当我选择不偷根节点的时候，左子树和右子树的偷或者不偷之间是完全没有关系的，它们之间应该是独立的关系，否则就会漏掉一些情况。

而底下这个写法才保证了左右之间的相互独立的关系。

此外再啰嗦一点，为什么这个时候，前后节点需要进行大小的比较？这里的比较有点类似上一道题里面最后的比较，因为0号位和1号位实际上取值的区间是不同的，所以它们之间的大小也没有绝对关系，当然要进行比较来取最大。而1里面因为存在包含关系，所以不比较也可以。

还有就是vector<int>，如果我想要定义一个vector，里面的0号位和1号位是两个0，那应该用大括号，而非小括号，小括号的vector<int> (0,0) 代表的是长度和初始值都为0的一个vector。

class Solution {
public:
    int rob(TreeNode* root) {
        if(!root){
            return 0;
        }
        vector<int> result = midgap(root);
        return max(result[0], result[1]);
    }
    vector<int> midgap(TreeNode* root){
        if(!root){
            return vector<int> {0,0};
        }
        vector<int> left = midgap(root->left);
        vector<int> right = midgap(root->right);
        int first = left[1] + right[1] + root->val;
        int second = max(left[0], left[1]) + max(right[0], right[1]);
        return vector<int> {first, second};
    }
};

最后附上GPT对于为什么三需要比较而一不需要的解释：

打家劫舍 III 中需要比较的原因：

在 打家劫舍 III 中，我们用一个二维的状态来表示每个节点的选择。对于每个节点，我们有两个可能的选择：

1. 不偷当前节点，这意味着我们可以选择左右子树的最大收益，max(left[0], left[1]) + max(right[0], right[1])。
2. 偷当前节点，这时我们必须计算左右子树的“不偷”收益，即 left[0] + right[0] + root->val。

由于 左右子树的选择是独立的，它们的最大值并不直接包含或依赖对方。因此，在 打家劫舍 III 中，我们需要分别比较左右子树中“偷或不偷”的收益，以便找到最优的方案。

打家劫舍 I 中的大小比较：

在 打家劫舍 I 中，问题是一维的，我们用 dp[i] 表示抢劫到第 i 个房子时的最大金额。状态转移方程是：

dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

这里的比较，实际上是一个 互斥 的选择，因为如果你选择了抢劫第 i 个房子，你就不能抢劫第 i-1 个房子，反之亦然。这就是为什么我们需要进行比较来找出最大的收益，因为我们有两种互斥的选择（偷或不偷）。

为什么 0号位和1号位取值区间不同，且需要比较：

在 打家劫舍 III 中，0号位 和 1号位 表示两种不同的状态：

• 0号位 表示“不偷当前节点”，它的值是左右子树的最大值（不包括当前节点的值）。
• 1号位 表示“偷当前节点”，它的值是当前节点的值加上左右子树不偷的最大值。

这两个状态的取值区间是不同的，因为它们分别代表了两种完全不同的策略：

• 不偷当前节点：你可以选择偷或者不偷左子树和右子树。
• 偷当前节点：你只能选择不偷左子树和右子树。

这两个状态之间并没有包含关系，所以必须进行比较，以确定偷或不偷哪个更有利。

为什么在打家劫舍 I 中不需要比较：

在 打家劫舍 I 中，状态转移是基于两个状态（抢劫当前房子或不抢劫），它们之间并没有独立性或者包含关系。直接用 max(dp[i-1], dp[i-2] + nums[i]) 就可以得到最大值。这是因为 dp[i-1] 和 dp[i-2] 表示相邻房子的状态选择，两者的选择是互斥的，并且不需要考虑它们之间的包含关系。

结论：

• 打家劫舍 III 中，需要比较左右子树的“偷或不偷”最大值，因为左右子树的选择是独立的，没有包含关系，必须独立选择。
• 打家劫舍 I 中，不需要额外比较，因为每个房子的选择是基于前一个房子的状态，两个选择是互斥的，不需要考虑包含关系。

所以，你的理解是对的，打家劫舍 III 中的大小比较类似于 打家劫舍 I 中的比较，但原因不同，主要是 独立选择 和 互斥选择 的问题。

希望这次解释能帮你更好地理解这个问题！如果有其他问题，随时问我。