LeetCode 198 · 1-D DP

House Robber, explained with a picture

A burglar who can’t hit two neighbours.

Medium1-D DP
▶ Watch it step by step

The problem

Houses along a street hold some money. You can’t rob two neighbouring houses (an alarm would go off). What is the most money you can take?

Input:  [2, 7, 9, 3, 1]
Output: 12   (2 + 9 + 1)

Picture it

Picture a burglar walking down a street of houses. At each house they decide: rob it (add its loot to the best total from two houses back) or skip it (keep the best total from the previous house). We keep two running totals and pick the better each time.

How to recognise it

  • You pick items from a line to maximise a total, under a rule that forbids neighbours (no two adjacent houses).
  • Every decision is yes or no for one house, and the choice at house i only interacts with house i − 1.
  • The best total up to house i can be built from the best totals up to the previous one or two houses.
  • Up to 100 houses (money at most 400) is far too many to try every subset: there are 2^100 of them.
  • "Choose a non-conflicting set with the largest value" on a line is the classic 1-D dynamic programming (DP) shape.

Start with brute force

For each house you have two options: skip it and look at the rest, or rob it and jump over its neighbour. Try both and keep the larger.

def rob_brute(houses):
    def go(i):                  # best loot from houses[i:]
        if i >= len(houses):
            return 0
        return max(go(i + 1), houses[i] + go(i + 2))
    return go(0)

This is correct, but each call makes up to two more, so time is exponential (about O(1.6^n)); for 100 houses that is more than 10^20 calls. The same suffixes are solved again and again. Space is O(n) for the recursion.

From brute force to the idea

  1. Find the waste. go(5) is reached from go(4) (skipped house 4) and from go(3) (robbed house 3). Its answer never changes, yet it is recomputed.
  2. Define two running answers. After looking at some houses, track skip, the best total when the latest house is not robbed, and take, the best total when it is robbed.
  3. Update both from the old values. For the next house with loot: the new skip is the better of the old two (the latest house is skipped either way), and the new take is the old skip plus loot (robbing it needs its neighbour untouched).
  4. Answer. After the last house, max(skip, take).

This is the key idea: the best total after each house depends only on two numbers, so you need two variables, not a table.

Note the single line skip, take = max(skip, take), skip + loot: Python builds the right side from the old values first. That order matters.

The key idea

best[i] = max(best[i − 1], best[i − 2] + money[i]). O(n), O(1) memory.

Python solution

def rob(houses):
    skip, take = 0, 0           # best total if the last house was skipped / robbed
    for loot in houses:
        skip, take = max(skip, take), skip + loot
    return max(skip, take)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(1.6^n): two branches per house, suffixes re-solvedO(n): recursion depth
Two variables (shown code)O(n): one pass, two operations per houseO(1): only skip and take

Edge cases

  • No houses ([]): returns 0.
  • One house ([5]): returns 5.
  • Two houses ([2, 1]): returns 2, the larger one, since they are neighbours.
  • Example [1, 2, 3, 1]: returns 4 (houses 1 and 3).
  • Example [2, 7, 9, 3, 1]: returns 12.
  • Zeros ([0, 0]): returns 0.
  • Big loot is not at the ends ([3, 10, 3, 1, 2]): returns 12; the 10 and the 2 beat 3 + 3 + 2.

Common mistakes

  • Greedily robbing the biggest house first: in [2, 1, 1, 2] that is not the best plan (the answer 4 takes both 2s).
  • Updating skip first and then computing take from the new skip. That lets you rob two neighbours (see the quiz).
  • Returning take alone, which is wrong when the last house is better skipped (for [2, 1] it gives 1).
  • Using take + loot, which adds every house together and ignores the neighbour rule.
Your turn: keep a bigger gap

Now robbing house i also sets off the alarm for houses two away, so any two robbed houses must be at least three positions apart (indices differ by 3 or more). Find the most money. For [3, 1, 1, 3] the answer is 6. Describe your approach, then write it if you like.

Compare with our answer

The earlier winner now has to come from three houses back when you rob the current one.

def rob_gap(houses):
    n = len(houses)
    best = [0] * (n + 1)        # best[i]: most loot from the first i houses
    for i in range(1, n + 1):
        best[i] = max(best[i - 1], best[max(i - 3, 0)] + houses[i - 1])
    return best[n]

rob_gap([3, 1, 1, 3]) is 6 and rob_gap([1, 2, 3, 1]) is 3. Time O(n), space O(n) (a rolling window of three values gives O(1)).

A strong answer mentions: best[i] as the best from the first i houses, choosing between skipping house i and robbing it on top of best[i - 3], clamping the index for small i, and that the original problem is the same idea with a gap of two.

Check what stuck

1. You need the largest total from a list of numbers where no two chosen numbers may be adjacent, and the list has up to 10^5 entries. Which approach fits best?

2. Why does the shown solution need only O(1) extra space?

3. A learner rewrites the update as two lines, skip = max(skip, take) then take = skip + loot. For which input is the result now wrong?

Score 60% or more and the lesson is marked complete.