198 打家劫舍
思路：首先判断给定的数组 nums 是否为空，如果是，则返回 0；如果只有一个元素，则返回该元素的值。
对于数组长度大于 1 的情况，创建一个长度为 nums.size() 的数组 dp，其中 dp[i] 表示在前 i 个房屋中能够获取的最大金额。
显然，dp[0] = nums[0]，即只有一座房屋时，获取的最大金额为该房屋的价值。
对于前两座房屋，获取的最大金额为 max(nums[0], nums[1])，即两者中的较大值。
对于第 i 座房屋，它可以选择被打劫或者不被打劫。如果选择打劫该房屋，那么获取的最大金额应该是前 i-2 座房屋中能够获取的最大金额加上该房屋的价值，即 dp[i-2]+nums[i]；如果选择不打劫该房屋，则获取的最大金额应该是前 i-1 座房屋中能够获取的最大金额，即 dp[i-1]。因此，第 i 座房屋的最大金额应该是这两种情况中的较大值，即 max(dp[i-2]+nums[i], dp[i-1])。
最后，返回 dp[nums.size()-1]，即前 nums.size() 座房屋中能够获取的最大金额。
1.动态规划
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
213 打家劫舍II
思路：首先判断给定的数组 nums 是否为空，如果是，则返回 0；如果只有一个元素，则返回该元素的值。
对于数组长度大于 1 的情况，我们需要将该问题转化为两个 "打家劫舍 I" 问题，即分别考虑从第 0 个房屋到第 n-1 个房屋和从第 1 个房屋到第 n 个房屋两个问题，并取它们的最大值。因此，我们可以使用一个 robRange 函数，来计算从第 start 个房屋到第 end 个房屋中能够获取的最大金额。
对于 robRange 函数，我们先判断区间长度，如果区间只有一个元素，则返回该元素的值。否则，创建一个长度为 nums.size() 的数组 dp，其中 dp[i] 表示在前 i 个房屋中能够获取的最大金额。
显然，dp[start] = nums[start]，即从第 start 个房屋开始获取的最大金额为该房屋的价值。
对于前两座房屋，获取的最大金额为 max(nums[start], nums[start+1])，即两者中的较大值。
对于第 i 座房屋，它可以选择被打劫或者不被打劫。如果选择打劫该房屋，那么获取的最大金额应该是前 i-2 座房屋中能够获取的最大金额加上该房屋的价值，即 dp[i-2]+nums[i]；如果选择不打劫该房屋，则获取的最大金额应该是前 i-1 座房屋中能够获取的最大金额，即 dp[i-1]。因此，第 i 座房屋的最大金额应该是这两种情况中的较大值，即 max(dp[i-2]+nums[i], dp[i-1])。
最后，返回 dp[end]，即从第 start 个房屋到第 end 个房屋中能够获取的最大金额。
最终，我们在主函数中分别计算从第 0 个房屋到第 n-1 个房屋和从第 1 个房屋到第 n 个房屋中能够获取的最大金额，并取它们的最大值作为最终结果。
1.动态规划
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
int result1 = robRange(nums, 0, nums.size() - 2);
int result2 = robRange(nums, 1, nums.size() - 1);
return max(result1, result2);
}
int robRange(vector<int>& nums, int start, int end){
if(end == start) return nums[start];
vector<int> dp(nums.size());
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
for(int i = start + 2; i <= end; i++){
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
};
337 打家劫舍 III
思路：首先定义一个 robTree 函数，用于计算以当前节点为根节点的二叉树中能够获取的最大金额。如果当前节点为空，返回一个长度为 2 的 vector，表示在当前节点为空时能够获取的最大金额为 0。
否则，我们需要考虑两种情况：选择打劫当前节点和不选择打劫当前节点。如果选择打劫当前节点，那么左右子树都不能被打劫，因此获取的最大金额应该是当前节点的价值加上左右子树中不能被打劫的节点的价值之和，即 cur->val + left[0] + right[0]。如果不选择打劫当前节点，那么左右子树可以被打劫，因此获取的最大金额应该是左右子树中能够获取的最大金额之和，即 max(left[0], left[1]) + max(right[0], right[1])。
最终，我们需要返回一个长度为 2 的 vector，其中第一个元素表示不打劫当前节点能够获取的最大金额，第二个元素表示打劫当前节点能够获取的最大金额。
在主函数 rob 中，我们调用 robTree 函数来计算整棵树能够获取的最大金额。由于根节点可以选择被打劫或者不被打劫，因此我们需要取两种情况中的较大值作为最终结果。
1.动态规划
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]);
}
vector<int> robTree(TreeNode* cur){
if(cur == NULL) return vector<int>{0, 0};
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
int val1 = cur->val + left[0] + right[0];
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
};
