~20 minutes · Day 62 · 1-D DP · Python
Tonight you meet House Robber: every house has money, but robbing two adjacent houses triggers the alarm. Interviewers like this because the local choice sounds simple, yet one greedy move can ruin the total. The pattern is to make the choice at each house while carrying the best totals from smaller prefixes.
At each house choose: rob it and add dp[i-2], or skip it and keep dp[i-1] — dp[i] = max(dp[i-1], nums[i] + dp[i-2]).
That one sentence is the whole lesson. Dynamic programming is useful when smaller overlapping subproblems can be solved once and reused (Wikipedia: dynamic programming). Here the repeated question is: “what is the best total up to this house?”
dp[i] means the best amount you can rob from houses 0..i.i, compare skipping it with taking it.0.The brute force recursion is O(2n): at each house, branch into two futures. That is easy to reason about, but it keeps asking the same suffix questions again and again.
def best_from(i):
if i >= len(nums): return 0
take = nums[i] + best_from(i + 2) # rob this house
skip = best_from(i + 1) # leave this house
return max(take, skip)
The better version keeps only the two earlier answers the transition needs. Python's max gives the larger of the skip and take totals.
def rob(nums):
prev2 = 0 # best up to i-2
prev1 = 0 # best up to i-1
for money in nums:
take = money + prev2 # rob current house
skip = prev1 # skip current house
cur = max(skip, take) # dp[i]
prev2, prev1 = prev1, cur # slide the window
return prev1
The trust point is the update order. prev2 and prev1 must still mean “two houses back” and “one house back” while you compute cur. Only after that do they slide forward.
A row of donation boxes has amounts written on them. You may take money from any boxes, but taking neighboring boxes is not allowed. Return the maximum amount.
Before opening the reveal: what should dp[i] mean, and what two choices should the transition compare?
It is the same pattern. Let dp[i] mean the best total from boxes 0..i. For each box, compare skipping it (dp[i-1]) with taking it (boxes[i] + dp[i-2]). The story changed; the invariant did not.
| Approach | Time | Space |
|---|---|---|
| Brute force (branch take or skip) | O(2n) | O(n) |
| DP (reuse the last two answers) | O(n) | O(1) |
The DP version spends no extra table because this transition only needs the previous two states. If writing the full dp array helps you see it first, do that; then compress it to two variables.
1. What does dp[i] mean in House Robber?
dp[i] is the best total for the prefix ending at house i, not the money inside one house.2. At house i, which choices are compared?
3. Spot the bug in this version:
prev2 = 0
prev1 = 0
for money in nums:
cur = max(prev1, money + prev2)
prev2 = cur
prev1 = cur
return prev1prev2 should become the old prev1, not cur. The tuple assignment keeps that old value long enough to slide correctly.4. Which prompt should make you think take-or-skip DP?
Solve House Robber on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — House Robber after your attempt, as the compare step. Listen for how he names the same take-or-skip recurrence.