---
description: '# Medium'
---

# 213. House Robber II

{% hint style="info" %}
Reference: [https://leetcode-cn.com/problems/house-robber-ii/solution/si-chong-jie-fa-213-da-jia-jie-she-ii-by-wang\_ni\_m/](https://leetcode-cn.com/problems/house-robber-ii/solution/si-chong-jie-fa-213-da-jia-jie-she-ii-by-wang_ni_m/)
{% endhint %}

> 由于这是一个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）.&#x20;
>
> 这个问题的要点就是，我们把首尾连接点设置成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)$$&#x20;

{% tabs %}
{% tab title="C++" %}
```cpp
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]);
        
    }

};
```


{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}
