今天上班只完成了一道题，被同事发现了，gg，果断溜回来做剩下的两道，加油吧xd，离新的工作越来越近了。
198.打家劫舍
打家劫舍1没有太多好说的，就是能搞定[i-2]和[i-1]取最大即可。
class Solution {
public:
int rob(vector<int>& nums) {
vector<int>dp(nums.size(),0);
if(nums.size() == 1)return nums[0];
if(nums.size() == 2)return max(nums[0],nums[1]);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2; i < nums.size();i++){
dp[i] = max(nums[i] + dp[i-2],dp[i-1]);
}
return dp[nums.size() - 1];
}
};213.打家劫舍II
这题我想的有点过于简单，导致看起来很乱，所以还是要先把打家劫舍1的搭建好，然后找起始结束，这样不乱，max(val1,val2)这种。我感觉我这个比随想录那个更清晰呢。用我这个！
class Solution
{
public:
int rob(vector<int> &nums)
{
int n = nums.size();
if (n == 1)
return nums[0];
if (n == 2)
return max(nums[0], nums[1]);
int val1 = robOnce(nums, 0, n - 2);
int val2 = robOnce(nums, 1, n - 1);
// cout << val1 << endl;
// cout << val2 << endl;
return max(val1, val2);
}
int robOnce(vector<int> &nums1, int start, int end)
{
if (end - start == 1)
return max(nums1[start], nums1[end]); // 这是n = 3的情况
vector<int> dp(end - start + 1, 0); // n = 4的情况啦
dp[0] = nums1[start];
dp[1] = max(nums1[start], nums1[start + 1]);
for (int i = 2; i < end - start + 1; i++)
{
dp[i] = max(dp[i - 1], dp[i - 2] + nums1[i + start]);
}
//for (int i = 0; i < end - start + 1; i++)
//{
// cout << dp[i] << ' ';
//}
//cout << endl;
return dp[end - start];
}
};337.打家劫舍III
通过vector<int>dp(2,0)，分成用当前结点和不用当前节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
vector<int> dp = robOnce(root);
return max(dp[0],dp[1]);
}
vector<int> robOnce(TreeNode *cur){
if(cur == nullptr)return {0,0};
vector<int>left = robOnce(cur->left);
vector<int>right = robOnce(cur->right);
vector<int> dp(2,0);
//偷当前节点
dp[1] = cur->val + left[0] + right[0];
//不偷当前节点
dp[0] = max(left[0],left[1]) + max(right[0],right[1]); //这步好难啊
return dp;
}
};不用当前节点的情况，要考虑他的子节点用还是不用比较大，这里比较难想。