198.打家劫舍
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();vector<int> dp(n);dp[0] = nums[0];if(n <= 1){return dp[0];}dp[1] = max(nums[0], nums[1]);for(int i=2; i<nums.size(); i++){dp[i] = max(dp[i-1], dp[i-2]+nums[i]);}return dp[n-1];}
};213.打家劫舍II
本题老毛病又犯了，这两个dp数组可以用一个函数进行复用，然后只要输入不同的下标即可，但是我却自己实现了这两个dp数组，在传值和合法性判断上，写起来麻烦不少，不过好在能正常执行。
还有一个问题是不知道max函数只能比较两个值，也不知道不能传两个迭代器，如果要比较三个数就只能调用两次max函数了。
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 中，我们用一个二维的状态来表示每个节点的选择。对于每个节点，我们有两个可能的选择：
- 不偷当前节点，这意味着我们可以选择左右子树的最大收益，
max(left[0], left[1]) + max(right[0], right[1])。 - 偷当前节点，这时我们必须计算左右子树的“不偷”收益，即
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 中的比较，但原因不同，主要是 独立选择 和 互斥选择 的问题。
希望这次解释能帮你更好地理解这个问题！如果有其他问题，随时问我。
