【算法练习Day40】打家劫舍打家劫舍 II打家劫舍 III

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

这一期到了打家劫舍的专题，说是专题但实际上只有一期，而且只有三道题，我们把这三道题放在一起讲，第一道题简单一些，后两道略有不同方向上的难度。但总体来看第一次做可能有一点难想到思路，其实代码实现还是可以的。

打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

题目要求相邻两间房子不能同时遭到盗窃。根据这一条件能够想清如何写出递推公式，则是解题的关键。

dp数组的含义：dp【i】代表了考虑当前第i个位置，是否被偷盗，所能盗得的最大金钱数，注意这里仅仅是考虑这个位置房子是否被偷盗，但是并不是一定会盗窃该房屋，具体是否盗窃该房屋，由递推公式决定。

递推公式： 对于此时遍历到的位置i有两种状态，偷或者不偷，如果是偷那么一定是当前房子被偷获得的价值nums【i】加上当前位置向前数的第二个位置所能获得的最大价值（同样的这个位置也不一定被偷）也就是dp【i-2】，偷该房子的最大获得钱币变成了nums【i】+dp【i-2】，如果不偷该房子，那么该房子的前一个位置就可以被考虑进来是dp【i-1】，它们两个取最大值

dp【i】=max（dp【i-2】+nums【i】，dp【i-1】）。这就是递推公式

我们要时刻记得当前位置i只是被考虑进来偷或者不偷，在递推公式取最大值之前，不能确定该位置一定偷或者不偷。

dp数组的初始化：dp【0】也就是起始位置，我们可以这样假想，加入房子只有一间，那么一定是偷盗了，才能获得最大金钱，所以dp【0】=nums【0】，我们还得为dp【1】初始化，因为递推公式需要用到i的前两个位置，dp【1】=max（nums【0】，nums【1】）是这两个屋子取最大值偷，因为相邻房子不能同时偷，同样可以想成一共只有两个房子，我们考虑偷第一间还是第二间。其余的位置初始化什么数都可以，因为并不能影响最后的答案。

遍历顺序：从前到后，很自然的遍历顺序，并没有考究。

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0)return 0;if(nums.size()==1)return nums[0];vector<int>dp(nums.size(),0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.size()-1];}
};

思路捋清了发现还是很简单的，但是第一次可能还是有部分想不明白，我刚做该题的思路是这样的：dp【1】初始化为nums【1】，然后最后比较的是偷第一间房屋和不偷哪个价值更大，这样做实际上是有弊端的例如测试用例为{2，1，1，2}时，这种情况是中间两间房子不偷盗，而两边偷盗获得的多。题目虽然要求相邻房子不能偷，但是这并不意味着我们一定要不停偷取才能获得最大金钱！！这就是曲解了dp数组的含义，dp【i】应是考虑i这个位置，而不是一定偷盗，这样想的才能解决这样的测试用例。

下面也给出错误的代码

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0)return 0;if(nums.size()==1)return nums[0];vector<int>dp(nums.size(),0);dp[0]=nums[0];dp[1]=nums[1];for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}return max(dp[nums.size()-1],dp[nums.size()-2]);}
};

相信对于上面的详细讲解，大家也对于这类问题的入门题目有了一定的了解，下面看一个进阶版本的。

打家劫舍 II

213. 打家劫舍 II - 力扣（LeetCode）

这道题的题目和上一道的唯一区别，在于房子围成一周，第一间房子与最后一间连接起来，并且也不能同时取。线性问题的数组，我们容易想到解题思路，那么环形的我们该如何思考呢？

将该环形数组分为三种情况，我们可以不看两边的房屋，只考虑中间部分 ，这是一种情况，这样中间部分可以像上一道题的思路一样，很轻松做出来，但是两边房屋该怎么办呢？别急还有另外两种情况，不考虑第一个房屋，和不考虑最后一个房屋。实际上这两种情况都包含了第一种情况，由于我们只是考虑这些房屋是否被偷盗，第二三种方法比第一种方法考虑的范围还要远，所以肯定是包含在内，而又由于第一间房屋和最后一间房屋并不能同时放在一起考虑，因为它们成环相连，所以我们只需取得二三种方法中较大得到金钱的那一个，即为最后的答案。将两个范围带入第一个题的函数中去，取得两个最大金钱值，取较大一个即可，看代码实现。

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];if(nums.size()==0)return 0;int result1=fun(nums,0,nums.size()-2);int result2=fun(nums,1,nums.size()-1);return max(result1,result2);}int fun(vector<int>&nums,int start,int end){if(start==end)return nums[start];//防止数组大小等于2vector<int>dp(nums.size(),0);dp[start]=nums[start];dp[start+1]=max(nums[start],nums[start+1]);for(int i=start+2;i<=end;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}return dp[end];}
};

代码实现是不是也很简单？但是想到思路可不是很容易，尤其对于没有做过很多环形数据的题人来说。特别说明：为什么函数实现里多了一个if（start==end）的判断，我们可能会想正常数组怎么可能传进来的的开始和结束指向同一个位置呢？这其实并不是我们传入错误，有些时候数据可能较短，比如只有两个数据的情况，这样的话按照我们上面的思路，就会出现start和end值一样的情况，我们就要直接返回一个数，因为如果这样再往下走会出现数组越界的情况。

这最后一道是二叉树和动态规划的交叉使用例题，也是树形dp的入门题目。这道题要求对于二叉树的使用要娴熟，而且还要穿插上动态规划的使用，第一次做同样也是有难度的例题。

打家劫舍 III

337. 打家劫舍 III - 力扣（LeetCode）

要求同样是相邻房屋不能被连续抢劫，所以就是取父节点就不能取两个子节点了！

前面的dp数组含义是一样的，不同的是递推公式需要注意一点。

我们要写递归函数来遍历整颗二叉树，需要两个dp数组分别代表左子树和右子树对于该节点偷或者不偷的两种情况分别对应的钱数。说一个误区，题目虽然是说一个父节点只有一个孩子节点，那为什么我们还需要两个dp呢？是因为我们不确定下一个子房子是左子树还是右子树上，所以我们要两个dp数组，而且也可能是一会像左一会向右，所以两边都需要记录，但是仅仅是需要每一个dp数组只有两个参数，dp【0】dp【1】，因为每次递归是会向下遍历的，上一层由系统栈存储，不需要担心每一个节点的数据会丢失。如果当前节点，我们选择偷那么值就是root-> val+leftdp【0】+rightdp【0】，因为取这个节点子节点都不能取，如果不取该节点就是leftdp【1】+rightdp【1】，它们两个最后取最大值就可以了。

细心的盆友肯定会发现，leftdp和rightdp的状态在我们遍历当前节点时候，不是还不能确定下来吗？所以这也是说明我们的遍历顺序是从下往上的后序遍历，把下面的状态推给上一层，这样就可以实现上一层的数据处理依赖下一层的数据了。

class Solution {
public:int rob(TreeNode* root) {vector<int>result=fun(root);return max(result[0],result[1]);}vector<int>fun(TreeNode* root){if(root==NULL)return vector<int>{0,0};vector<int>left=fun(root->left);vector<int>right=fun(root->right);int val1=max(left[0],left[1])+max(right[0],right[1]);int val2=root->val+left[0]+right[0];return {val1,val2};}
};

后序遍历的方法，可以让我们从下向上传递状态转移，遇到空子树，返回的相当于取和不取都是0。最后到根节点往上返回根节点取和不取的两种金钱数，取最大。注意return返回的val1，和val2的顺序不能颠倒，他们是有确定的含义的，返回上一层时候需要调用下一层的两个状态，写反了一定会出问题。

最后，对于递归向上返回时是如何工作的，大家可以自行实现一下，不要只知道代码大概模板，就通过了，做递归类问题最重要的是要知道递归每一步是如何返回的，这样更有利于深刻理解。

总结：

今天我们完成了打家劫舍、打家劫舍 II、打家劫舍 III 三道题，相关的思想需要多复习回顾。接下来，我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~