算法思想：
采用动态规划的思想。当前的最大金额是由前两个状态决定的。
i表示当前的状态。
偷i： dp[i] = dp[i-2] +nums[i]
不偷i：dp[i] = dp[i-1]
初始化
dp[0] = 0
dp[1] = max(dp[0], dp[1])
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
if(nums.size() == 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[nums.size()-1];
}
};
算法思想：
打家劫舍1的升级版本。
就是考虑首尾元素不能同时选取的问题。
如果选取了尾元素，那数组就变成[1,n)的打家劫舍1问题，不选取尾元素，变成[0,n-1)的打家劫舍1问题。
class Solution {
public:
int dajiajieshe1(vector<int>& nums3)
{
vector<int> dp(nums3.size(), 0);
dp[0] = nums3[0];
if(nums3.size()==1)
return dp[0];
dp[1] = max(nums3[0], nums3[1]);
if(nums3.size()==2)
return dp[1];
for(int i=2;i<nums3.size();i++)
{
cout<<"i:"<<i<<endl;
dp[i] = max(dp[i-1], dp[i-2]+nums3[i]);
}
return dp[nums3.size()-1];
}
int rob(vector<int>& nums)
{
if(nums.size()==1)
return nums[0];
vector<int> nums1(nums.begin(), nums.end()-1);
int res1 = dajiajieshe1(nums1);
vector<int> nums2(nums.begin()+1, nums.end());
int res2 = dajiajieshe1(nums2);
return max(res1, res2);
}
};
算法思想：
动态规划和递归的结合。
可以用一个dp[0]和dp[1]表示当前节点是偷还是不偷。
当前节点偷的时候
res =cur + left[0] + right[0]
当前节点不偷的时候
res = max(left[0], left[1]) + max(right[0], right[1])
class Solution {
public:
vector<int> digui(TreeNode* root)
{
if(root==NULL)
return vector<int> {0,0};
vector<int> left = digui(root->left);
vector<int> right = digui(root->right);
int rootselect = root->val + left[0] + right[0];
int rootnotselect = max(left[0],left[1]) + max(right[0], right[1]);
return vector<int>{rootnotselect, rootselect};
}
int rob(TreeNode* root) {
vector<int> dp = digui(root);
return max(dp[0], dp[1]);
}
};
