Practice: House Robber
No two neighbours.
A burglar plans to rob houses along a street, but alarms go off if two neighbouring houses are robbed on the same night. Each house holds a different amount. What's the most the burglar can take? Pause, and think about the last house.

- Houses in a row
- No two neighbours
- The most money?
Rob it or skip it
At each house, there are two choices. Rob it, and add its money to the best total from two houses back. Or skip it, and keep the best total from the house before. We only need to remember two numbers as we walk along. Run it. The best haul is twelve, from houses one, three, and five.
def rob(houses):
two_back, one_back = 0, 0
for money in houses:
two_back, one_back = one_back, max(one_back, two_back + money)
return one_back
print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))12 10
Shrinking the table
Often the table only ever looks back one or two steps. Then you don't need the whole table, just a couple of variables. That turns O of N memory into O of one. Climbing stairs and Fibonacci can be shrunk in exactly the same way.
| key | value |
|---|---|
| Choice | rob, or skip |
| Rob | two back + money |
| Skip | one back |
| Memory | O(1) with two variables |
Summary
At each house, take the better of robbing it or skipping it. Two variables are enough. Next, measuring how different two words are.
Key takeaways- max(skip, rob)
- Two variables
- O(n) time, O(1) space