House Robber — choice DP in one dimension
House Robber — choice DP in one dimension
You're walking a street of houses, each with cash. Rob any subset, but two adjacent houses trip a shared alarm. Maximize your take. Archetypal 1D choice DP.
The pattern
Let dp[i] = best loot considering the first i+1 houses. At house i:
- Skip it. Best is
dp[i-1]. - Take it. Pocket
houses[i], but you couldn't have touchedi-1, so adddp[i-2].
Take the max: dp[i] = max(dp[i-1], dp[i-2] + houses[i]).
From O(n) to O(1) space
Look at the recurrence — dp[i] only needs the previous two values. Drop the array, keep two ints.
Interviewers love when you write the array version first (clarity) then compress (optimization). Shows you understand why the compression is safe.
Why this generalizes
"Choice at each index, look back k steps" appears everywhere — paint fence, delete-and-earn, max-sum non-adjacent subsequence.
Common pitfalls
- Empty input — return 0.
- Off-by-one on base cases — n=1 and n=2 need explicit handling.
- Circular streets (House Robber II) — first and last also adjacent. Solve twice: excluding first, excluding last.
Try it
- Extend
rob_rollingto also return the indices you robbed. - Solve House Robber II (circular): run rolling on
houses[:-1]andhouses[1:], take max.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Write
max_non_adjacent(nums)that returns the largest sum you can get by picking numbers from the list such that no two chosen numbers are next to each other. Return 0 for an empty list. - Exercise 2
Write
rob(nums)that returns the maximum money a robber can take from a row of houses, given they cannot rob two neighboring houses on the same night. - Exercise 3
Write
rob_circular(nums)for a ring of houses where the first and last are neighbors. You still cannot rob two adjacent houses. Handle the edge cases of 0 or 1 house.