213. House Robber II

# Medium

Reference: https://leetcode-cn.com/problems/house-robber-ii/solution/si-chong-jie-fa-213-da-jia-jie-she-ii-by-wang_ni_m/

由于这是一个circle，不管考虑是否抢劫house 1或者2或者n，都是一回事，因此只有两种情况，是否抢house 1，会影响后面一系列的抉择，当然如果将house 2作为连接点也是一回事。假设要抢劫房子[1, 2, 3, 4, 5, 6]，如果抢劫1，那么就不能抢劫6，则dp1计算1-5的最大值，至于抢劫了1不能抢劫2等等都相当于#198，让dp1[1:5]去做决定，因此不用特别将这种情况区分开来；如果不抢劫1，那么可以抢劫2-6，则dp2计算2-6的最大值。由于只有抢劫1或者不抢劫1两种选择会影响最后的钱，所以最后返回max(dp1, dp2）.

这个问题的要点就是，我们把首尾连接点设置成1，就将一个环形数组拆分成了两个非穿行数组，如果将守卫连接点设置成其他数，则需重新生成两个数组。

Solution:

1. Two dps, dp1 means maximum money in nums[0: n-2].

2. dp2 means maximum money in nums[1: n-1].

3. return max(dp1[n-2], dp2[n-1]).

4. Time complexity = $O(2n)$ = $O(n)$ . Space complexity = $O(2n)$ = $O(n)$

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        // edge case
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);
        
        // regular case
        int dp1[nums.size()]; // compute nums[0:end-1]
        int dp2[nums.size()]; // compute nums[1:end]
        
        // initialize dp1 & dp2
        dp1[0] = nums[0];
        dp1[1] = max(nums[0], nums[1]);
        dp2[0] = 0;
        dp2[1] = nums[1];
        
        // compute dp1
        for(int i = 2; i < nums.size()-1; i ++) {
            dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i]);
        }        
        // compute dp2
        for(int i = 2; i < nums.size(); i ++) {
            dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i]);
        }
        
        return max(dp1[nums.size()-2], dp2[nums.size()-1]);
        
    }

};

Second Tab