【力扣每日一题】2023.9.17 打家劫舍Ⅱ

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

打家劫舍2在1的基础上增加了一个规则，那就是房屋是首尾相连的。

这对我们解题有什么影响呢？

唯一的影响就是我们偷了第一间屋子就不能偷最后一间屋子了。

最终情况可以分为两种，第一种就是可以偷第一间屋子而不能偷最后一间屋子，第二种就是可以偷最后一间屋子而不能偷第一间屋子。

在第一种情况之下，我们直接忽略最后一间屋子，然后按照打家劫舍1的方法算出答案，这时求出的答案是符合打家劫舍2的要求（房屋相连）的，因为房屋首尾相连唯一影响的就是首尾两个屋子不能同时偷到。不过此时得到的答案不一定是最大的答案。

 

因此我们还有第二种情况，我们直接忽略第一间屋子，再求出答案。

 

最后我们把两个情况下得到的答案选个最大的返回即可。

关于dp数组的初始化，第一个dp忽略最后一个房屋，所以按照推导公式（dp[ i ] = max( dp[ i - 1 ] , dp[ i - 2] + nums[ i ])），我们应该初始化前两个房屋的数值。

而第二个dp忽略第一个房屋，因此是从第二个房屋开始初始化两个房屋，综合一下，我们初始化涉及到的房屋是前三个，所以当房屋数量小于3时是属于特殊情况，我们要特殊处理，就直接返回数组里最大的一个数即可。

最后就是dp数组的含义了，因为dp1忽略最后一个房屋，所以对于dp数组的含义是没有影响的，dp[ i ]就是等于当遍历到下标为 i 的房屋时能获取到的最大答案。

但是dp2就不一样了，因为dp2是从第二个房屋开始算的，所以dp2[ 0 ]实际上等于下标为1的房屋的数值，因此dp2[ i ]的含义就是当遍历到下标为 i + 1的房屋时能获取到的最大答案。

因此两个dp的递推公式会有稍许不一样，具体看看代码就可以理解的。

代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<=3){       //长度小于3,特殊情况特殊处理
            int res=0;
            for(int num:nums) res=max(res,num);
            return res;
        }
        vector<int>dp1(n-1,0);
        vector<int>dp2(n-1,0);
        //dp1为不偷最后一家
        dp1[0]=nums[0],dp1[1]=max(nums[0],nums[1]);
        //dp2位不偷第一家
        dp2[0]=nums[1],dp2[1]=max(nums[1],nums[2]);
        for(int i=2;i-1;i++){
            dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);
            dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i+1]);
        }
        return max(dp1[n-2],dp2[n-2]);
    }
};