198.打家劫舍
当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了
动规五部曲
确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
dp数组如何初始化
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历
for(inti=2;i<nums.size();i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}
213.打家劫舍II
考虑包含首元素，不包含尾元素
考虑包含尾元素，不包含首元素
二者取大的
introb(vector<int>&nums){if(nums.size()==0)return0;if(nums.size()==1)returnnums[0];intresult1=robRange(nums,0,nums.size()-2);// 情况二intresult2=robRange(nums,1,nums.size()-1);// 情况三returnmax(result1,result2);}// 198.打家劫舍的逻辑introbRange(vector<int>&nums,intstart,intend){if(end==start)returnnums[start];vector<int>dp(nums.size());dp[start]=nums[start];dp[start+1]=max(nums[start],nums[start+1]);for(inti=start+2;i<=end;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}returndp[end];}
337.打家劫舍III
后序遍历二叉树
确定递归函数的参数和返回值
求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组
参数为当前节点
返回数组为dp数组
确定终止条件
在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
if (cur == NULL) return vector<int>{0, 0};
确定遍历顺序
后序遍历
递归左节点，得到左节点偷与不偷的金钱
递归右节点，得到右节点偷与不偷的金钱
确定单层递归的逻辑
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
vector<int>left=robTree(cur->left);// 左vector<int>right=robTree(cur->right);// 右// 偷curintval1=cur->val+left[0]+right[0];// 不偷curintval2=max(left[0],left[1])+max(right[0],right[1]);return{val2,val1};
网友评论