代码随想录算法训练营第三十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III。

198.打家劫舍

力扣题目链接

classSolution{public:introb(vector<int>&nums){if(nums.size()<2)returnnums[0];//dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。vector<int>dp(nums.size(),0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(inti=2;i<nums.size();i++){//偷与不偷dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}returndp[nums.size()-1];}};

213.打家劫舍II(成环)

力扣题目链接
对于一个数组，成环的话主要有如下三种情况：

• 1.考虑不包含首尾元素
• 2.考虑包含首元素，不包含尾元素
• 3.考虑包含尾元素，不包含首元素
  2、3包含了1情况

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

337.打家劫舍III（二叉树）

力扣题目链接

• 必须后序遍历，因为必须得到左右节点偷不偷的最大价值才可以进行节点计算

/** * 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) {} * }; */classSolution{public:introb(TreeNode*root){vector<int>re=robTree(root);returnmax(re[0],re[1]);}//长度为2：0不偷 1偷vector<int>robTree(TreeNode*cur){if(cur==NULL)returnvector<int>{0,0};vector<int>left=robTree(cur->left);vector<int>right=robTree(cur->right);//偷curintval1=cur->val+left[0]+right[0];//不偷cur,左右节点可以偷也可以不偷intval2=max(left[1],left[0])+max(right[0],right[1]);return{val2,val1};}};