# 213. House Robber II

## Approach 1: Keep track of amount robbed using DP

The approach is very similar to House Robber (which I strongly recommend reading first)

Since the array is circular this time, we will keep track of two lists of sums, one with `nums[0]` (`dpl`) and one without `nums[0]` (`dpr`).  This way when we reach the last element, we will only check the array that does not have `nums[0]` to make sure that first and the last houses are not robbed together.

```python
class Solution(object):
    def rob(self, nums):
        """
        https://leetcode.com/problems/house-robber-ii/description/
        :type nums: List[int]
        :rtype: int
        """
        lea = len(nums)
        if lea == 0:
            return 0
        if lea == 1:
            return nums[0]
        if lea == 2:
            return max(nums)
        if lea == 3:
            return max(nums[0], nums[1], nums[2])
        if lea == 4:
            return max(nums[1] + nums[3], nums[0] + nums[2])
        dpl = [0] * lea
        dpl[0], dpl[1], dpl[2], dpl[3] = nums[0], nums[1], nums[0] + nums[2], nums[3] + nums[0]
        dpr = [0] * lea
        dpr[0], dpr[1], dpr[2], dpr[3] = nums[0], nums[1], nums[2], nums[3] + nums[1]
        for i in range(4, lea-1):
            dpl[i] = nums[i] + max(dpl[i-2], dpl[i-3])
            dpr[i] = nums[i] + max(dpr[i-2], dpr[i-3])
        dpr[-1] = nums[-1] + max(dpr[-4], dpr[-3])
        return max(dpl[-2], dpl[-3], dpr[-1], dpr[-2])
```

Another added difference between this and House Robber I is that our base case has expanded from 3 to 4, because this time we are storing `dpl[3]` as `nums[3] + nums[0]` and `dpr[3]` as `nums[3] + nums[1]` to make sure `dpl` contains the first element while `dpr` does not.

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(N)*