DSAMotivator

House Robber

Medium·📈 1-D Dynamic Programming·Open on LeetCode ↗

Pick a set of values from a row so that no two picks are next to each other, and the total is as large as possible.

nums = [4, 9, 3, 1, 11, 2, 8]step 1/16
4
9
3
1
11
2
8
0
1
2
3
4
5
6
best
take
0
skip
0

Two running totals: best ending in a robbery, and best ending in a skip.

1def rob(nums):
2    take, skip = 0, 0
3    for n in nums:
4        take, skip = skip + n, max(skip, take)
5    return max(take, skip)
Read the 16 steps as text
  1. 1Two running totals: best ending in a robbery, and best ending in a skip.
  2. 2House 0 holds 4.
  3. 3Rob it and you must have skipped house -1: 0 + 4 = 4. Skip it and you keep the better of 0 and 0: 0.
  4. 4House 1 holds 9.
  5. 5Rob it and you must have skipped house 0: 0 + 9 = 9. Skip it and you keep the better of 4 and 0: 4.
  6. 6House 2 holds 3.
  7. 7Rob it and you must have skipped house 1: 4 + 3 = 7. Skip it and you keep the better of 9 and 4: 9.
  8. 8House 3 holds 1.
  9. 9Rob it and you must have skipped house 2: 9 + 1 = 10. Skip it and you keep the better of 7 and 9: 9.
  10. 10House 4 holds 11.
  11. 11Rob it and you must have skipped house 3: 9 + 11 = 20. Skip it and you keep the better of 10 and 9: 10.
  12. 12House 5 holds 2.
  13. 13Rob it and you must have skipped house 4: 10 + 2 = 12. Skip it and you keep the better of 20 and 10: 20.
  14. 14House 6 holds 8.
  15. 15Rob it and you must have skipped house 5: 20 + 8 = 28. Skip it and you keep the better of 12 and 20: 20.
  16. 16Best plan ending either way: 28.

The idea

Greedy fails here, and it's worth seeing exactly how. "Always take the biggest remaining" picks 11 from [4, 9, 3, 1, 11, 2, 8], which forbids both neighbours and loses more than it gains. Local best is not global best when your choices constrain each other.

So think one house at a time and be honest about what the choice depends on. At each house you either take it — which requires that you skipped the one before — or you don't, in which case you keep whatever the best was up to the previous house.

That gives two running totals: the best where the last house was taken, and the best where it wasn't. Every new house updates both from the previous pair. Nothing further back matters, which is why this needs two numbers and not a table.

This is the whole of one-dimensional DP in miniature: find the smallest piece of history that makes the next decision well-defined, then carry only that.

The approach

  1. 1Track two totals: `take` — the best if the most recent house was robbed — and `skip` — the best if it wasn't.
  2. 2At each house: the new `take` is the old `skip` plus this house's value, since you may only rob it if you skipped the previous one.
  3. 3The new `skip` is the better of the old `take` and the old `skip` — having skipped this one, either history is allowed.
  4. 4Update both simultaneously from the old pair, then answer with the larger at the end.

Complexity

Time
O(n)
Space
O(1)

One pass, two integers. The textbook version keeps a full dp array; it is the same recurrence with n times more memory than it needs.

Code

def rob(nums):
    take, skip = 0, 0
    for n in nums:
        take, skip = skip + n, max(skip, take)
    return max(take, skip)

What goes wrong

  • •Updating `take` and `skip` in sequence rather than together. Overwrite `skip` first and the new `take` is computed from a value that already belongs to this step, which quietly allows robbing two adjacent houses.
  • •Assuming the answer is `take`. If the last house is small, the best plan may well end on a skip — return the larger of the two.
  • •Assuming values are positive and dropping the `max` in `skip`. It happens to work here, but the habit breaks the moment negatives are allowed.