House robber: choose or skip

House robber

A row of houses holds money, say [2, 7, 9, 3, 1]. You may rob any set of houses but never two adjacent ones, and the goal is to maximize the haul.

Apply the lesson 9-1 discipline, starting with the meaning. table[i] is the best haul considering only the first i houses.

Then the recurrence, which comes from the single choice at house i, using 1-indexed positions.

• Skip it and you keep the best of the first i−1 houses, which is table[i-1].
• Rob it and you take houses[i-1] plus the best of the first i−2, since the neighbor is off-limits, which is table[i-2] + houses[i-1].

table[i] = max(table[i−1], table[i−2] + houses[i−1])

Those two options cover every possibility, because house i is either robbed or it is not.

Base cases are table[0] = 0 for no houses and table[1] = houses[0] for one house, where the only choice is to take it.

This choose-or-skip recurrence is the backbone of dozens of problems, including stock cooldowns, deleting numbers, and skipping exams. Learn the shape rather than the story.

Filling the haul table

The printed table is the running best-so-far.

def rob(houses):
    n = len(houses)
    if n == 0:
        return 0
    table = [0] * (n + 1)
    table[1] = houses[0]
    for i in range(2, n + 1):
        table[i] = max(table[i - 1],
                       table[i - 2] + houses[i - 1])
    print(table)
    return table[n]

print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))

Output

[0, 2, 7, 11, 11, 12]
12
[0, 5, 5, 6, 10]
10

The i - 1 in houses[i - 1] is the index shift, since table[i] covers the first i houses and the i-th house sits at index i−1. Writing the meaning down first is what keeps that straight.

Entry 4 staying at 11 is the interesting cell. Robbing house 4 for 3 would mean giving up house 3, and 2 + 9 = 11 beats 7 + 3 = 10, so the max picks the skip.

Entry 5 rises to 12 by robbing house 5 for 1 on top of table[3] = 11, giving 2 + 9 + 1.

The table never decreases, which is a useful sanity check. table[i-1] is always one of the two candidates, so more houses can never mean a worse haul.

The second call is the case a naive alternating rule fails. [5, 1, 1, 5] gives 10 by taking the two 5s, which are positions 1 and 4 and not adjacent.

Because robbing house i forbids robbing house i−1, so the best compatible past is the first i−2 houses.

table[i-1] includes plans that rob house i−1, and adding house i to one of those would break the rule. table[i-2] cannot contain house i−1 at all, so it is safe to build on.

The no-adjacent constraint is encoded exactly there, in that one index. Nothing else in the code mentions adjacency.

That is the general check worth carrying: every constraint in a DP problem must show up somewhere in the recurrence, and finding where is how you verify the recurrence is right.

If a constraint appears nowhere, the table is solving a different problem. Using table[i-1] here would compute the sum of all the houses, which is the answer to a question with no adjacency rule at all.

rob_circle

The follow-up interviewers love, where the street is a circle so the first and last houses are adjacent too.

def rob(houses):
    n = len(houses)
    if n == 0:
        return 0
    table = [0] * (n + 1)
    table[1] = houses[0]
    for i in range(2, n + 1):
        table[i] = max(table[i - 1], table[i - 2] + houses[i - 1])
    return table[n]

def rob_circle(houses):
    if len(houses) == 1:
        return houses[0]
    return max(rob(houses[1:]), rob(houses[:-1]))

print(rob_circle([2, 3, 2]))
print(rob_circle([1, 2, 3, 1]))
print(rob_circle([5]))

Output

3
4
5

The insight is a case split. Any valid plan on a circle cannot rob both house 0 and the last house, so it lives entirely inside houses[1:] or entirely inside houses[:-1].

Both of those slices are ordinary straight streets, and rob already solves those, so no new recurrence is needed.

The two cases can overlap, in that a plan robbing neither end appears in both slices, and that is harmless. The max only needs each optimum to be covered by some case, not covered exactly once.

The single-house case needs its own line, because houses[1:] and houses[:-1] are both empty and the answer 5 would be lost.

For [2, 3, 2] the answer is 3, since the two 2s are now neighbors through the wrap, and for [1, 2, 3, 1] it is 4 from the 1 and the 3.

This reduce-to-a-solved-problem move is itself an interview pattern worth naming out loud, and it beats writing a circular recurrence from scratch.

The maximum haul is 10, from robbing house 1 and house 4 for 5 + 5.

Those two houses are not adjacent, with houses 2 and 3 sitting between them, so the plan is legal.

A greedy rob-every-other-house rule gets 6 either way, taking 5 + 1 from the odd positions or 1 + 5 from the even ones. Both miss because the pattern is fixed in advance.

A rob-the-biggest-first greedy gets this one right by accident, taking a 5 and then the other 5. It fails on [4, 5, 4], where it grabs the 5, blocks both neighbors, and returns 5 where 4 + 4 = 8 was available.

This is another reminder after lesson 8-2 that plausible greedy rules lose to DP when choices interact. Here taking a house changes what is available next, which is exactly the coupling greedy cannot see.