Week3-Day6 | 在打劫劫舍(1)上分类讨论

首先可以看一下我的打家劫舍(1)的题解打家劫舍(1)题解链接
回到本题，题目在原有基础上加上了环
分类讨论一下:

1.当要偷第一个房子的时候，能偷到范围是哪些?
相邻的不能偷，最后一个房子不能偷
那么就是 $nums[0]+rob(nums[2:n-1])$
2.当不偷第一个房子时能偷的范围?
排除掉第一个，从第二个房子到最后都可以偷
$rob(nums[1:n])$

那么我们利用打家劫舍1的代码再分类讨论下，两种情况取最大值就是答案

$code$

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob1(vector<int>&nums,int l, int r){
        int x=0, y=0;
        for(int i=l;i<r;i++){
            int t=max(y,x+nums[i]);
            x=y;
            y=t;
        }
        return y;
    }
    int rob(vector<int>& nums) {
        int n =nums.size();
        //偷第一个房子
        int x=nums[0]+rob1(nums, 2, n-1);
        //不偷第一个
        int y=rob1(nums, 1, n);
        return max(x,y);
    }
};

打卡区 alt