Rob the most cash from a row of houses without hitting two neighbours. Carry the best haul so far, one house at a time.
▼The problem
A row of houses each holds some cash. Rob the most you can without robbing two adjacent houses.
Example: [2, 7, 9, 3, 1] → 12 (houses 1, 3 and 5).
The solution
def rob(houses):
prev, best = 0, 0 # best two back, best so far
for cash in houses:
prev, best = best, max(best, cash + prev)
return bestTranscript
House Robber. A row of houses, each holding some cash. Rob as much as you can, but if you rob two houses next to each other, the alarm goes off. What's the most you can take?
Take two, seven, nine, three, one. Grabbing the biggest houses doesn't work: nine and seven are neighbors. The best haul is two, nine and one: twelve.
Trying every safe combination grows exponentially. But look at the last house. Either you skip it, and keep the best haul from the houses before it. Or you rob it, and add its cash to the best haul from two houses back. Take whichever is bigger.
That's dynamic programming: solve the small problems first, write each answer down, and build on them.
So walk left to right, filling in the best haul so far. The first house: two. The second: seven beats two, so seven. The third: skip it and keep seven, or rob it: nine plus two is eleven. Eleven wins. The fourth: keep eleven, or three plus seven is ten. Keep eleven. The last: keep eleven, or one plus eleven is twelve. The answer is twelve.
Each step only looks two houses back, so two variables are enough. One pass: linear time, and constant space.
Skip it or rob it, and remember the best. That's House Robber.