leetcode213. 打家劫舍 II

思路

注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

假设数组nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0, n-2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1, n-1]。

class Solution {
public:
    int robRange(vector<int>nums,int start,int end){
        int first=nums[start],second=max(nums[start],nums[start+1]);
        for(int i=start+2;i<end;i++){
            int temp=second;
            second=max(first+nums[i],second);
            first=temp;
        }
        return second;
    }
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        else if(n==2)return max(nums[0],nums[1]);
        return max(robRange(nums,0,n-1),robRange(nums,1,n));
    }
};