**Solution with discussion**https://discuss.leetcode.com/topic/80721/python-solution-with-detailed-explanation

**House Robber II** https://leetcode.com/problems/house-robber-ii/?tab=Description

**Memoization**:

- Use another variable first which indicates if first house is included or not in the current DFS path.
- Based on first, at index N-1, we will set use (the case where we rob a house) to 0 or nums[i].
- Caching will be 2D. At index i, we now ask what is the maximum money we can rob given we robbed house 0 or not.

```
class Solution(object):
def helper(self, i, nums, cache, first):
N = len(nums)
if i >= N:
return 0
if i in cache and first in cache[i]:
return cache[i][first]
cache.setdefault(i, {})
if i == 0:
use, not_use = nums[i]+self.helper(i+2, nums, cache, True), self.helper(i+1, nums, cache, False)
elif i + 1 == N and first:
use, not_use = 0, self.helper(i+1, nums, cache, first)
else:
use, not_use = nums[i]+self.helper(i+2, nums, cache, first), self.helper(i+1, nums, cache, first)
cache[i][first] = max(use, not_use)
return cache[i][first]
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = {}
return self.helper(0, nums, cache, False)
```

**Dynamic Programming**

- We split the problem into two sub problems.
- Intuition: Any solution will either include nums[0] or nums[1].
- Problem 1: Maximum value we can rob using house 0 to N-2
- Problem 2: Maximum value we can rob using house 1 to N-1
- Solution is the maximum or Problem1 and Problem2.
- https://discuss.leetcode.com/topic/14504/9-lines-0ms-o-1-space-c-solution

```
class Solution(object):
def sub_rob(self, nums, lo, hi):
"""
:type nums: List[int]
:rtype: int
"""
result = prev_prev = prev = 0
for idx in range(lo, hi+1):
result = max(prev_prev+nums[idx], prev)
prev_prev = prev
prev = result
return result
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return sum(nums)
return max(
self.sub_rob(nums, 0, len(nums)-2),
self.sub_rob(nums, 1, len(nums)-1)
)
```