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

198.打家劫舍

题目链接：198.打家劫舍
递归五步曲分析：

1. 确定dp数组下标及其含义
   dp[i]: 表示在[0~i]之间的房间进行偷窃的最高金额为dp[i]
2. 确定递推公式
   偷盗当前房屋 i : dp[i - 2] + nums[i]
   不偷当前房屋 i : dp[i - 1]
   取最高金额，所以递推公式为：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3. 初始化
   dp[0] = nums[0];
   dp[1] = max(nums[0], nums[1])
4. 确定遍历顺序
   从前面房前是否被偷来确定时候偷后面的房间，所以遍历顺序是从前往后的。
5. 举例推倒
   

classSolution{public:introb(vector<int>&nums){if(nums.size()==1)returnnums[0];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-1],dp[i-2]+nums[i]);}returndp[nums.size()-1];}};

时间复杂度：O(n)
空间复杂度：O(n)

213.打家劫舍II

题目链接：213.打家劫舍II
首尾任选其一。
房间首尾相连：只包含首元素不包含尾元素和只包含尾元素不包含首元素两种情况取最大值。
这道题看题解了，我对问题的拆分能力还待提升。

classSolution{private:introbRange(vector<int>&nums,intstart,intend){// 左闭右闭区间if(start==end)returnnums[start];vector<int>dp(nums.size(),0);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-1],dp[i-2]+nums[i]);}returndp[end];}public:introb(vector<int>&nums){if(nums.size()==1)returnnums[0];intresult1=robRange(nums,0,nums.size()-2);// 包含首元素，不包含尾元素intresult2=robRange(nums,1,nums.size()-1);// 不包含首元素，包含尾元素returnmax(result1,result2);}};

时间复杂度：O(n)
空间复杂度：O(n)

337.打家劫舍III

题目链接：337.打家劫舍III
dp数组在树形结构上进项状态转移，秒啊！
递归三步曲+动规五步曲

1. 确定递归函数的参数和返回值 (及dp数组含义)
   每个节点有 偷与不偷 两种状态所获得的金钱。
   用一个长度为2的dp数组表示。
   dp[0]表示不偷该节点获得的最大金额。
   dp[1]表示 偷 该节点获得的最大金额。
   所以递归参数，是节点
   递归返回值是一个长度为2的数组。

   vector<int>robTree(TreeNode*cur)

2. 确定终止条件 （dp初始化）
   如果是空节点，偷 与 不偷 ， 金额都为0.

   if(cur==nullptr)returnvector<int>{0,0};

3. 确定遍历顺序
   需要通过递归返回值来进行下一步的计算，所以采用后序遍历。
   递归左节点，递归右节点

4. 确定当前节点的递归逻辑 (dp递推公式)
   如果偷当前节点，其左右孩子就不能偷, 最大金额为：val1 = cur->val + left[0] + right[0]
   left[0]表示不偷左孩子的最大金额；
   right[0]表示不偷右孩子的最大金额；
   如果不偷当前节点，左右孩子就可以偷，最大金额为左右孩子偷 或 不偷的最大金额：
   val2 = max(left[0], left[1]) + max(right[0], right[1])
   当前节点的状态为：{val2, val1}

5. 举例推导
   

classSolution{private:// dp[0]:不偷； dp[1]:偷vector<int>traversal(TreeNode*cur){if(cur==nullptr)return{0,0};vector<int>left=traversal(cur->left);vector<int>right=traversal(cur->right);intval1=cur->val+left[0]+right[0];// 偷当前节点intval2=max(left[0],left[1])+max(right[0],right[1]);// 不偷当前节点return{val2,val1};}public:introb(TreeNode*root){vector<int>result=traversal(root);returnmax(result[0],result[1]);}};

时间复杂度：O(n)
空间复杂度：O(log n)