【代码随想录算法训练Day45】LeetCode 198.打家劫舍、LeetCode 213.打家劫舍II、LeetCode 337.打家劫舍III

dp数组含义：考虑偷前i家后的最大钱币为dp[i]
递推公式：dp[i]=max(dp[i-2]+nums[i],dp[i-1])
初始化：dp[0]=nums[0],dp[1]=max(dp[0],dp[1]),dp[i]=任意值
遍历顺序：从小到大

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

本题的关键在于解环，如何能够取消环对我们取元素的影响。
答案是分成两部分，前一部分只取首元素，不取尾元素，另一部分则只取尾元素，这样再取两者的最大值即可。

class Solution {
public: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-2]+nums[i],dp[i-1]);return dp[end];}int rob(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];int res1=robRange(nums,0,nums.size()-2);int res2=robRange(nums,1,nums.size()-1);return max(res1,res2);}
};

dp数组的含义：只有一个长度为2的一维dp数组，dp[0]不偷该节点获得的最大金钱，dp[1]偷该节点获得的最大金钱。

class Solution {
public:vector<int> robTree(TreeNode* cur){if(!cur) return vector<int>{0,0}; vector<int> left=robTree(cur->left);vector<int> right=robTree(cur->right);int v1=cur->val+left[0]+right[0];int v2=max(left[0],left[1])+max(right[0],right[1]);return {v2,v1};}int rob(TreeNode* root) {vector<int> res=robTree(root);return max(res[0],res[1]);}
};

偷！都可以偷！