# House Robber
https://leetcode.com/problems/house-robber/
Example of [[dp]].
Intuition, when robbed the first house, or we skipped it, the problem is reduced...
## Approach 1: Memoization
```python
dp: dict[int, int] = {}
n = len(nums)
def rob_from(i):
if i >= n:
return 0
if i in dp:
return dp[i]
ans = max(
rob_from(i + 1),
rob_from(i + 2) + nums[i]
)
dp[i] = ans
return ans
return rob_from(0)
```
## Approach 2: DP
A tabular approach isn't necessarily "bottom-up"!
```python
n = len(nums)
max_amount = [None] * (n + 1)
max_amount[n] = 0 # no house left, cannot obtain more money
max_amount[n - 1] = nums[n - 1] # one house left, rob it
for i in range(n - 2, -1, -1):
# rob from i-th house, i included
max_amount[i] = max(
max_amount[i + 1], # don't rob this, rob next
max_amount[i + 2] + nums[i] # rob this and second next
)
return max_amount[0]
```
## Approach 3: Optimized DP
Observe that `max_amount[i]` only depends on the previous two values at `i + 1` and `i + 2`. Space complexity also optimized.
```python
n = len(nums)
rob_next_next = 0 # there's no next next, no house left!
rob_next = nums[n - 1] # there's one house left, rob it
for i in range(n - 2, -1, -1):
current = max(rob_next, rob_next_next + nums[i])
rob_next_next = rob_next
rob_next = current
return rob_next
```
An alternative code
```python
t1 = 0 # max amt robbed up to the current house
t2 = 0 # max amt robbed up to before the current house
for current in nums:
t1, t2 = max(current + t2, t1), t1
return t1
```
Think of `t1` and `t2` as two thieves
- `t1` leaves a note of max amount that can be robbed up to this house
- `t2` enters the house, communicate this info with `t1` through walkie-talkie. At this time, `t1` is at the next house
- The two thieves decide should they rob or not