DSA House Robber

The problem

The house robber problem asks for the largest total from a row of houses. Each house holds some money. No two neighbouring houses may both be taken.

The input is a list of amounts, one per house. The output is one total. The houses themselves are not listed in the answer.

cases = [
    ([2, 7, 9, 3, 1], 12),
    ([5, 1, 1, 5], 10),
    ([2, 7, 9], 11),
    ([5], 5),
    ([], 0),
]
for houses, expected in cases:
    print("houses", houses, "best total:", expected)

On the first street the best plan takes 2, 9 and 1. That plan sums to 12. The two end houses of the second street give 5 + 5 = 10.

Intuition: taking the bigger neighbour fails

A greedy rule scans the street with one local choice. When the next house holds more, it skips the current house. When the current house holds at least as much, it takes it and skips the next.

Each choice looks sensible on its own. The rule never looks at the whole street. A chain of deferrals can walk straight past the best plan.

def greedy(houses):
    taken = []
    i = 0
    while i < len(houses):
        if i + 1 < len(houses) and houses[i + 1] > houses[i]:
            i += 1
        else:
            taken.append(houses[i])
            i += 2
    return taken

houses = [2, 7, 9, 3, 1]
taken = greedy(houses)
print("greedy took:", taken)
print("greedy total:", sum(taken))
print("best total:", 12)

Greedy defers at 2, then defers at 7. It finally takes 9 and 1, for a total of 10. The best plan takes 2 as well and reaches 12.

The failure is quiet. Greedy still returns a legal plan. It just returns a smaller total.

Brute force: take or skip every house

The brute force tries both choices at every house. Take the house and jump two places. Or skip it and move one place. The larger total wins.

calls = 0

def brute(houses, i):
    global calls
    calls += 1
    if i >= len(houses):
        return 0
    take = houses[i] + brute(houses, i + 2)
    skip = brute(houses, i + 1)
    return max(take, skip)

for houses in [[2, 7, 9, 3, 1], [5, 1, 1, 5]]:
    calls = 0
    print("houses", houses, "best:", brute(houses, 0), "calls:", calls)

The answers are right. The calls already repeat work. The best total from a suffix of the street is recomputed on many branches.

A street twice as long makes the branching far worse. The article counts that growth in the complexity section.

The optimal solution: best total up to each house

The state is best(i), the largest total from the first i houses. That one sentence defines the table.

At each house there are two options. Taking it adds its money to the best total two houses back. Skipping it keeps the best total so far. The larger option becomes the new best.

def rob(houses):
    best = 0
    two_back = 0
    for money in houses:
        take = money + two_back
        new_best = max(best, take)
        two_back = best
        best = new_best
    return best

cases = [[2, 7, 9, 3, 1], [5, 1, 1, 5], [2, 7, 9], [5], []]
for houses in cases:
    print("houses", houses, "best total:", rob(houses))

All five cases from section 1 pass. The greedy street now answers 12. Only the last two totals are kept, so no table is stored.

Walkthrough: one street, house by house

Follow the first street, [2, 7, 9, 3, 1]. The state after each house is the best total so far. The printed line also shows the take option at that house.

houses = [2, 7, 9, 3, 1]
best = 0
two_back = 0
for money in houses:
    take = money + two_back
    new_best = max(best, take)
    print("house", money, "take gives:", take, "best so far:", new_best)
    two_back = best
    best = new_best
print("answer:", best)

House 9 is taken with house 2, giving 11. House 3 offers 3 + 7 = 10, so the best stays 11. House 1 offers 1 + 11 = 12, and that becomes the answer.

Complexity

The scan visits each house once and does a fixed amount of work there, so the time is O(n) for n houses.

Only two totals are carried from step to step, so the extra space is O(1).

calls = 0

def brute(houses, i):
    global calls
    calls += 1
    if i >= len(houses):
        return 0
    return max(houses[i] + brute(houses, i + 2), brute(houses, i + 1))

for n in [8, 12, 16]:
    houses = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3][:n]
    calls = 0
    brute(houses, 0)
    print("houses", n, "brute force calls:", calls, "scan steps:", n)

The scan steps grow with the street. The brute force calls grow far faster. The printed counts carry the claim.

Edge cases and pitfalls

An empty street has no houses to take. Its answer is 0. Code that reads a first house before checking would fail on it.

One house is always taken. Two houses give the larger of the pair, never their sum.

def rob(houses):
    best = 0
    two_back = 0
    for money in houses:
        take = money + two_back
        new_best = max(best, take)
        two_back = best
        best = new_best
    return best

print("empty street:", rob([]))
print("one house:", rob([5]))
print("two houses:", rob([4, 9]))
print("two equal houses:", rob([7, 7]))
print("all small, one big:", rob([1, 1, 20, 1, 1]))

The common pitfall is adding a house to the best total one house back. That total may already include its neighbour. The take option must reach two houses back.