198.打家劫舍dp数组含义考虑前i个房间偷到的最大钱数为dp[i]递推公式不偷第i个房间则最大钱数为dp[i-1];偷第i个房间最大钱数为dp[i-2]nums[i]取最大值即为dp[i] max(dp[i-1], dp[i-2]nums[i])初始化由于递推公式用到了i-1和i-2所以初始化dp[0]和dp[1]分别是nums[0]和max(nums[0],nums[1]);遍历顺序为了用到第0个和第1个元素从前向后从2开始遍历即可class Solution { public: int rob(vectorint nums) { if(nums.size()1) return nums[0]; if(nums.size()2) return max(nums[0],nums[1]); vectorint dp(nums.size()); dp[0] nums[0]; dp[1] max(nums[0],nums[1]); for(int i2;inums.size();i){ dp[i] max(dp[i-1],dp[i-2]nums[i]); } return dp[nums.size()-1]; } };213.打家劫舍II在打家劫舍的基础上加了限制条件-前后不能同时偷所以分为两种情况不考虑首元素不考虑尾元素所以设计新的打家劫舍函数输入数组起始索引终止索引在首尾闭区间的范围体现在初始化和for循环中应用打家劫舍即可。class Solution { public: int rob(vectorint nums) { if(nums.size()1) return nums[0]; int result1 ROB(nums, 0, nums.size()-2); int result2 ROB(nums, 1, nums.size()-1); return max(result1,result2); } int ROB(vectorint nums, int start, int end){ if(start end) return nums[start]; vectorint dp(nums.size()); dp[start] nums[start]; dp[start1] max(nums[start],nums[start1]); for(int i start2; iend; i){ dp[i] max(dp[i-1],dp[i-2]nums[i]); } return dp[end]; } };337.打家劫舍III本题为递归和动态规划的结合。递归返回当前节点偷或者不偷的最大价值用一个长度为2的一维数组表示递归三部曲1.返回类型和参数列表返回一个长度2的一维数组参数列表就传入树节点即可2.终止条件当遍历到空节点时偷或者不偷价值都是0所以返回{0,0};3.递归逻辑先分别递归调用左孩子和右孩子的返回值得到两个长度为2的数组下面计算当前节点偷或不偷的最大钱数当前节点偷cur-val left[0] right[0] 解释当前节点价值左孩子都不偷的价值当前节点不偷max(left[0],left[1])max(right[0],right[1]) 解释左右孩子各自的最大价值之和动规五部曲1.dp数组含义dp[0]和dp[1]分别代表当前节点不偷和偷对应的最大价值;2.递推公式和递归逻辑一致首先调用左右子树得到左右子树各自偷或不偷的最大价值从而推出当前节点偷或不偷的最大价值3.初始化与终止条件一致空节点对应起始初始化为{0,0}4.遍历顺序本题dp数组长度为2直接显式写出先0后1 或者 先1后0 都可以。注本题的二叉树遍历顺序是后序遍历左右中因为要知道左右子节点的返回结果才能递推到中间节点。class Solution { public: int rob(TreeNode* root) { vectorint result ROB(root); return max(result[0],result[1]); } vectorint ROB(TreeNode* cur){ if(curNULL) return {0,0}; vectorint leftROB(cur-left); vectorint rightROB(cur-right); int val0 max(left[0],left[1])max(right[0],right[1]); int val1 cur-val left[0] right[0]; return {val0,val1}; } };