力扣算法刷题 Day 38 （打家劫舍专题）

198 打家劫舍题目链接点击此处思路考虑当前房屋是否被偷取决于前两间房屋的情况。dp五部曲如下dp数组含义dp[i]表示下标从0到i的房屋能偷盗的最大价值递推公式: 如果dp[i-1]不偷那么偷当前的如果dp[i-1]偷考虑两者取最大值dp[i] max(dp[i-2] value[i],dp[i-1]);初始化:dp[0] value[0], dp[1] max(value[0],value[1]);遍历顺序从左到右模拟文章详解添加链接描述classSolution{public:introb(vectorintnums){if(nums.size()1){returnnums[0];}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题目链接点击此处思路相比于上一道题在最后一家的处理上需要考虑特殊情况。我们考虑三种情况不包括首尾、包括首、包括尾三种情况分别处理取最大值即可。classSolution{public:introb(vectorintnums){if(nums.size()0)return0;if(nums.size()1)returnnums[0];intresult1robRange(nums,0,nums.size()-2);// 情况二intresult2robRange(nums,1,nums.size()-1);// 情况三returnmax(result1,result2);}// 198.打家劫舍的逻辑introbRange(vectorintnums,intstart,intend){if(endstart)returnnums[start];vectorintdp(nums.size());dp[start]nums[start];dp[start1]max(nums[start],nums[start1]);for(intistart2;iend;i){dp[i]max(dp[i-2]nums[i],dp[i-1]);}returndp[end];}};打家劫舍III题目链接添加链接描述思路换成了树后序遍历保证递归文章详解添加链接描述classSolution{public:introb(TreeNode*root){vectorintresultrobTree(root);returnmax(result[0],result[1]);}// 长度为2的数组0不偷1偷vectorintrobTree(TreeNode*cur){if(curNULL)returnvectorint{0,0};vectorintleftrobTree(cur-left);vectorintrightrobTree(cur-right);// 偷cur那么就不能偷左右节点。intval1cur-valleft[0]right[0];// 不偷cur那么可以偷也可以不偷左右节点则取较大的情况intval2max(left[0],left[1])max(right[0],right[1]);return{val2,val1};}};