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

198.打家劫舍力扣题目链接classSolution{public:introb(vectorintnums){if(nums.size()2)returnnums[0];//dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。vectorintdp(nums.size(),0);dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(inti2;inums.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(vectorint nums) { if(nums.size()1) return nums[0]; vectorintre1(nums.begin(),nums.end()-1); vectorintre2(nums.begin()1,nums.end()); return max(robRange(re1),robRange(re2)); } int robRange(vectorint nums) { if(nums.size()2) return nums[0]; vectorintdp(nums.size(),0); dp[0]nums[0]; dp[1]max(nums[0],nums[1]); for(int i2;inums.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){vectorintrerobTree(root);returnmax(re[0],re[1]);}//长度为20不偷 1偷vectorintrobTree(TreeNode*cur){if(curNULL)returnvectorint{0,0};vectorintleftrobTree(cur-left);vectorintrightrobTree(cur-right);//偷curintval1cur-valleft[0]right[0];//不偷cur,左右节点可以偷也可以不偷intval2max(left[1],left[0])max(right[0],right[1]);return{val2,val1};}};