213. House Robber II.md

213. House Robber II

思路

这道题是198.House Robber拓展，现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了。

此题的关键点就在于：如果把第一家和最后一家分别去掉，各算一遍能抢的最大值，两个值较大的一个即为所求。

知道了这个关键点后此题就和198题没有任何区别了，198有两个思路，所以此题也有两种思路，时间复杂度均为O(n)，空间复杂度均为O(1)， 详见198题解，这里直接给出代码。

C++

思路一

class Solution {
private:
    int rob_helper(vector<int>& nums, int start, int end){
        if(start > end) return 0;
        if(start == end) return nums[end];
        
        int tmp, dp1 = nums[start], dp2 = max(nums[start], nums[start + 1]);
        for(int i = 2; i < end - start + 1; i++){
            tmp = dp2;
            dp2 = max(dp2, nums[start + i] + dp1);
            dp1 = tmp;
        }
        return dp2;
    }
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return nums.empty() ? 0 : nums[0];
        return max(rob_helper(nums, 0, n - 2), rob_helper(nums, 1, n - 1));
    }
};

思路二

class Solution {
private:
    int rob_helper(vector<int> &nums, int left, int right) {
        int rob = 0, notRob = 0;
        for (int i = left; i <= right; i++) {
            int preRob = rob, preNotRob = notRob;
            rob = preNotRob + nums[i];
            notRob = max(preRob, preNotRob);
        }
        return max(rob, notRob);
    }
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return nums.empty() ? 0 : nums[0];
        return max(rob_helper(nums, 0, n - 2), rob_helper(nums, 1, n - 1));
    }
};