198. 打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
nums.insert(nums.begin(),0);
int n=nums.size();
vector<int> dp(n,INT_MIN);
dp[0]=0;
dp[1]=nums[1];
for(int i=2; i<n; i++){
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[n-1];
}
};dp[i]：截止下标i(包含i）的房子，所能打劫的最大金额
转移方程：考虑nums[i]是否被打劫，只有两种可能：
- 抢，那么为了不触发警报，nums[i-1]一定不能被打劫，只能从i-2转移而来
- 不抢，则nums[i-1]可以被抢，最大金额就等于dp[i-1]
引入空房间作为虚拟头，初始化更简单，且不影响最终结果。
213. 打家劫舍 II
class Solution {
public:
int rob_range(vector<int>& nums, int left, int right) {
if(left==right)
return nums[left];
int n=nums.size();
vector<int> dp(nums.size(),INT_MIN);
dp[left]=nums[left];
dp[left+1]=max(nums[left+1],nums[left]);
for(int i=left+2; i<=right; i++){
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[right];
}
int rob(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
int amount1=rob_range(nums,0,nums.size()-2);
int amount2=rob_range(nums,1,nums.size()-1);
return max(amount1,amount2);
}
};上题的变种，题目可以拆分为两种情况：抢第一间或不抢第一间。分别处理取最大即可
337. 打家劫舍 III
class Solution {
public:
pair<int,int> rob_tree(TreeNode* root){
if(root==nullptr)
return {0,0};
auto [left_0, left_1]=rob_tree(root->left);
auto [right_0, right_1]=rob_tree(root->right);
int root_1=root->val+left_0+right_0;
int root_0=max(left_0,left_1)+max(right_0,right_1);
return {root_0,root_1};
}
int rob(TreeNode* root) {
auto [root_0, root_1]=rob_tree(root);
return max(root_0,root_1);
}
};状态转移：定义rob_tree返回的是pair：{不抢根的最大值，抢根的最大值}
采用后续遍历，利用子树的结果构建当前结果，也是分治的思想，即把当前问题拆解为规模更小的子问题，直到空树，一定为{0，0}。
对于当前层的计算逻辑，分两种情况：
- 抢根，这时子树的根一定不能抢，否则触发报警，所以此时金额为root->val+left_0+right_0
- 不抢根，这时子树的选择就随意了，不论子树抢或者不抢，均不会触发警报，所以分别取最大值即可：max(left_0,left_1)+max(right_0,right_1)