# 213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

```
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.
```

**Example 2:**

```
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
```

```cpp
// Dynamic Programming
int rob(vector<int>& nums) { // time: O(n); space: O(n)
    if (nums.empty()) return 0;
    int n = nums.size();
    if (n == 1) return nums[0];
    // money1: Rob the first and not rob the last
    // money2: Not rob the first and rob the last
    vector<int> money1(n, 0), money2(n, 0); 
    for (int i = 0; i < n; ++i) {
        if (i != n - 1)
            money1[i] = max((i > 0 ? money1[i - 1] : 0), (i > 1 ? money1[i - 2] : 0) + nums[i]);
        if (i != 0) 
            money2[i] = max((i > 0 ? money2[i - 1] : 0), (i > 1 ? money2[i - 2] : 0) + nums[i]);
    }
    return max(money1[n - 2], money2[n - 1]);
}
```

```cpp
// Space Optimized Dynamic Programming
int rob(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size();
    if (n <= 1) return n ? nums[0] : 0;
    return max(base_rob(nums, 0, n - 2), base_rob(nums, 1, n - 1));
}
int base_rob(vector<int>& nums, int l, int r) {
    if (l > r) return 0;
    int two_step = 0, one_step = 0;
    for (int i = l; i <= r; ++i) {
        int cur = max(one_step, two_step + nums[i]);
        two_step = one_step;
        one_step = cur;
    }
    return one_step;
} 
```

{% content-ref url="198.-house-robber" %}
[198.-house-robber](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/198.-house-robber)
{% endcontent-ref %}