House Robber Explained: Dynamic Programming with Take or Skip

House robber is the problem that makes dynamic programming feel small. There is no table to fill and no tricky state: at every position you make one decision, and two numbers remember everything that decision needs. If climbing stairs was your first recurrence, this is the first one where a choice appears, and the same take-or-skip shape runs through knapsack, stock trading and scheduling problems.

The problem it solves

Houses stand in a row, each holding some amount of money. You cannot take from two adjacent houses. What is the largest total you can collect? For [2, 7, 9, 3, 1] the answer is 12, from houses 0, 2 and 4: 2 + 9 + 1.

Checking every allowed subset is exponential, and the obvious greedy, "take the biggest value first", is wrong. On [8, 9, 8] it grabs the 9, which blocks both 8s, and ends with 9 instead of 16. One large value can cost you two neighbours that are worth more together.

The intuition

Walk left to right and ask one question at each house: take it or skip it?

• Take it, and the previous house must have been skipped. The total is "best so far with the previous house skipped" plus this value.
• Skip it, and nothing is forbidden. The total is the best so far, whether or not the previous house was taken.

So two running totals are enough: skip, the best total where the last house was not taken, and take, the best total where it was. Each step computes the new pair from the old pair:

• new take = old skip + value
• new skip = max(old skip, old take)

The answer at the end is the larger of the two. The more common textbook form, best[i] = max(best[i - 1], best[i - 2] + value), is the same recurrence written with one array; the two variables are that array with everything older than two steps thrown away.

Watch it run

The animation labels the houses as five nightly fees, [2, 7, 9, 3, 1], with a take row and a skip row under them. Night 0: take for 0 + 2 = 2, skip for 0. Night 1: take for 0 + 7 = 7, skip for max(0, 2) = 2. Night 2: take for 2 + 9 = 11, skip for 7. Night 3: take for 7 + 3 = 10, skip for 11. Night 4: take for 11 + 1 = 12, skip for 11. The answer is max(11, 12) = 12, and the last frame shows the winning set, 2 + 9 + 1, beating the tempting 7 + 3.

The code

The lesson's version with two rolling totals, plus the edge cases:

def rob(values):
    skip, take = 0, 0                          # best so far with the last house unused / used
    for v in values:
        skip, take = max(skip, take), skip + v # taking v needs the previous house skipped
    return max(skip, take)

print(rob([2, 7, 9, 3, 1]))                    # 12
print(rob([5, 5, 10, 100, 10, 5]))             # 110
print(rob([]), rob([4]), rob([2, 1, 1, 2]))    # 0 4 4

Interviewers often ask which houses you picked. Keep the full best array and walk it backwards: if a house did not change the best total, it was skipped; if it did, it was taken and its neighbour was not:

def rob_with_houses(values):
    best = [0] * (len(values) + 1)             # best[i]: best total from the first i houses
    for i, v in enumerate(values, start=1):
        best[i] = max(best[i - 1], (best[i - 2] if i >= 2 else 0) + v)
    picked, i = [], len(values)
    while i > 0:                               # walk back: did house i-1 change the answer?
        if best[i] == best[i - 1]:
            i -= 1                             # skipped
        else:
            picked.append(i - 1)               # taken, so its neighbour was skipped
            i -= 2
    return best[-1], picked[::-1]

print(rob_with_houses([2, 7, 9, 3, 1]))        # (12, [0, 2, 4])

The greedy that fails, and the circular variant, where the first and last houses are neighbours. Solve the row twice, once without the first house and once without the last:

def greedy_biggest_first(values):
    taken, total = set(), 0
    for i in sorted(range(len(values)), key=lambda i: -values[i]):
        if i - 1 not in taken and i + 1 not in taken:
            taken.add(i)
            total += values[i]
    return total

print(greedy_biggest_first([8, 9, 8]), rob([8, 9, 8]))   # 9 16

def rob_circle(values):
    if len(values) == 1:
        return values[0]
    return max(rob(values[1:]), rob(values[:-1]))   # first and last can't both be taken

print(rob_circle([2, 3, 2]), rob_circle([1, 2, 3, 1]))   # 3 4

Everything against a brute force over every allowed subset, on 1,000 random rows:

import random
from itertools import product

def brute(values, circle=False):
    best = 0
    for mask in product([0, 1], repeat=len(values)):
        if any(mask[i] and mask[i + 1] for i in range(len(values) - 1)):
            continue
        if circle and len(values) > 1 and mask[0] and mask[-1]:
            continue
        best = max(best, sum(v for v, m in zip(values, mask) if m))
    return best

random.seed(16)
ok = True
for _ in range(1000):
    vals = [random.randint(0, 20) for _ in range(random.randint(0, 12))]
    total, picked = rob_with_houses(vals)
    ok &= rob(vals) == total == brute(vals) == sum(vals[i] for i in picked)
    ok &= all(b - a > 1 for a, b in zip(picked, picked[1:]))
    if vals:
        ok &= rob_circle(vals) == brute(vals, circle=True)
print(ok)                                      # True

The complexity

• Brute force over subsets: O(2^n).
• Plain recursion on rob(i) = max(rob(i + 1), value + rob(i + 2)) without a cache recomputes the same suffixes and is exponential too, following the Fibonacci numbers.
• Memoized or tabulated: O(n) time and O(n) space.
• Two rolling totals: O(n) time and O(1) space. Recovering the chosen houses needs the full O(n) array.

Where it goes wrong

• Updating one variable before reading it. Writing take = skip + v and then skip = max(skip, take) uses the new take. Update both at once, as the tuple assignment does, or keep a temporary.
• Returning take instead of the max. The best answer may skip the last house.
• Assuming values are positive. With zeros the code still works. With negative values, skipping is always allowed, so they are never taken; say so if the interviewer changes the input.
• Forgetting the one-house circle. values[1:] and values[:-1] are both empty for a single house, so that case returns the value directly.

When it shows up in interviews

It shows up as a medium question, and it is often the first one where the interviewer wants to see you state a recurrence before coding it. Expect the variants: the circular row, which is house robber II; houses on a binary tree, where each node returns a take and skip pair to its parent; and "which houses?", which needs the array. Outside interviews it is the shape of any schedule with a cool-down, such as booking gigs that need a rest day after each show, or picking non-overlapping time slots in a strict sequence.

How to say it in an interview

"At each house I either take it, which means the previous one was skipped, or skip it and keep the best so far. I carry two numbers: the best total with the last house skipped, and with it taken. Each step, new take is old skip plus the value, and new skip is the max of the old pair. The answer is the max at the end. That is O(n) time and O(1) space; if you want the houses themselves I keep the best array and walk it backwards."

The circular version is in house robber in a circle, and climbing stairs covers the recurrence without a choice that this one builds on.