代码随想录算法训练营第36期DAY50

DAY50

如果写累了就去写套磁信吧。

198打家劫舍

1. class Solution {
2. public:
3.     int rob(vector<int>& nums) {
4.         vector<int> dp(nums.size());
5.         dp[0]=nums[0];
6.         if(nums.size()==1) return nums[0];
7.         dp[1]=max(nums[0],nums[1]);
8.         for(int i=2;i<nums.size();i++){
9.             dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
10.         }
11.         return dp[nums.size()-1];
12.     }
13. };

213打家劫舍ii

数组成环，分三种情况：

1. 不考虑首尾
2. 不考虑首，仅考虑尾
3. 不考虑尾，仅考虑首

注意，考虑不代表必选。

那么情况2 3 就已经包括了情况1。

写函数来解决，就不用挪数组。

注意是从dp[start]开始赋值

1. class Solution {
2. public:
3.     int getres(vector<int>nums,int start,int end){
4.         vector<int> dp(nums.size());
5.         if(start==end) return nums[start];
6.         dp[start]=nums[start];
7.         dp[start+1]=max(nums[start],nums[start+1]);
8.         //注意i的初值
9.         for(int i=start+2;i<=end;i++)
10.         dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
11.         return dp[end];
12.     }
13.     int rob(vector<int>& nums) {
14.         if(nums.size()==1) return nums[0];
15.         int res1=getres(nums,0,nums.size()-2);
16.         int res2=getres(nums,1,nums.size()-1);
17.         if(res1>res2) return res1;
18.         else return res2;
19.     }
20. };

337打家劫舍 iii--树形DP

能想到：后序遍历，把孩子信息传到父节点：若孩子之和没有大于父节点，则买入父节点。反之买入孩子之和。还要注意一些复杂的逻辑。还是不会。

节点之间的状态影响进一步计算，那么是动态规划

状态dp表示抢或不抢，抢的话，就不能动两个孩子；不抢的话，就要考虑动孩子了。

1. 暴力递归

超时了：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14. //这个递归还挺难想
15.     int rob(TreeNode* root) {
16.         if(root==nullptr) return 0;
17.         if(root->left==nullptr&&root->right==nullptr) return root->val;
19.         int val1=root->val;
20.         if(root->left) val1+=rob(root->left->left)+rob(root->left->right);
21.         if(root->right) val1+=rob(root->right->left)+rob(root->right->right);
23.         int val2=rob(root->left)+rob(root->right);
24.         return max(val1,val2);
25.     }
26. };

1. 动态规划

记录当前偷与不偷得到的最大金额。

树形DP，在树上做状态转移。

求一个节点，偷与不偷两个状态分别所得到的金钱，返回值是一个长度为2的数组。

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<int> getres(TreeNode* cur){
15.         if(cur==nullptr) return {0,0};
17.         vector<int> left=getres(cur->left);
18.         vector<int> right=getres(cur->right);
20.         int val1=cur->val+left[0]+right[0];
21.         int val2=max(left[0],left[1])+max(right[0],right[1]);
22.         return {val2,val1};
23.     }
24.     int rob(TreeNode* root) {
25.         vector<int> res=getres(root);
26.         return max(res[0],res[1]);
27.     }
28. };