# LC 213. House Robber II

### [Problem link](https://leetcode.com/problems/house-robber-ii/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

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 a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night** .

Given an integer array <code>nums</code> representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police** .

**Example 1:**

Input: nums = [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: nums = [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.

**Example 3:**

Input: nums = [1,2,3]
Output: 3

**Constraints:**

- <code>1 <= nums.length <= 100</code>
- <code>0 <= nums[i] <= 1000</code>

## Solution 1 - DP
#### Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        def calMax(a):
            if len(a) <= 2:
                return max(a)

            n = len(a)
            dp = [0] * n
            dp[0] = a[0]
            dp[1] = max(a[0], a[1])

            for i in range(2, n):
                dp[i] = max(dp[i - 2] + a[i], dp[i - 1])

            return dp[-1]

        if len(nums) <= 1:
            return max(nums)

        return max(calMax(nums[1:]), calMax(nums[:-1]))

#### C++

class Solution {
public:
    int calMaxProfit(vector<int>& nums, int start, int end) {
        if (end - start + 1 <= 2) {
            return *max_element(nums.begin() + start, nums.begin() + end + 1);
        }

        vector<int> dp(nums.size(), 0);
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }

    int rob(vector<int>& nums) {
        if (nums.size() <= 2) {
            return *max_element(nums.begin(), nums.end());
        }
        int max1 = calMaxProfit(nums, 0, nums.size() - 2);
        int max2 = calMaxProfit(nums, 1, nums.size() - 1);
        return max(max1, max2);
    }
};

class Solution {
public:
    int calMaxProfit(vector<int>& nums, int left, int right) {
        if (left > right) {
            return 0;
        }
        int n = nums.size();
        vector<int> cache(n, -1);
        function<int(int)> dfs = [&](int i) {
            if (i < left) {
                return 0;
            }
            if (cache[i] != -1) {
                return cache[i];
            }
            cache[i] = max(dfs(i - 2) + nums[i], dfs(i - 1));
            return cache[i];
        };
        return dfs(right);
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        int a = nums[0] + calMaxProfit(nums, 2, n - 2);
        int b = calMaxProfit(nums, 1, n - 1);
        return max(a, b);
    }
};

## Solution 2 - DP
#### C++

class Solution {
public:
    int calMaxProfit(vector<int>& nums, int left, int right) {
        int f0 = 0;
        int f1 = 0;
        for (int i = left; i <= right; i++) {
            int f2 = max(f0 + nums[i], f1);
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        int a = nums[0] + calMaxProfit(nums, 2, n - 2);
        int b = calMaxProfit(nums, 1, n - 1);
        return max(a, b);
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 1 | O(n) | O(1) |

## Note
sol1:
既然是排成一圈, 那就選一間房子為頭或是尾巴, 選第0間房子最方便