codebrew

House Robber

Medium
Dynamic Programming

At each house choose the better of robbing it (plus two back) or skipping it.

Animated Rolling DP Trace

twoBack = 0 and oneBack = 0: before the first house, there's nothing to take.
StopDP tableExport
Houses
  • CH1 twoBack
  • CH2 oneBack

Problem

You are given an array where each value is the money available in one house along a street. Choose a set of houses to rob so that no two neighboring houses are chosen, and return the largest total amount you can collect.

Examples

Input: nums = [2, 7, 9, 3, 1]

Output: 12

Rob houses with amounts 2, 9, and 1. They are non-adjacent and total 12.

Input: nums = [5, 1, 1, 5]

Output: 10

Rob the first and last houses for a total of 10.

The Goal

Each house holds some money. Rob a set of houses, never two next door, and return the largest total.

For [2, 7, 9, 3, 1], robbing the houses with 2, 9 and 1 gives 12.

At every house you choose: skip it, or rob it and give up the house before it.

Two legal choices

Skip house i and keep the best total through i - 1. Or rob it, and add its money to the best total through i - 2.

Key Idea: Skip or Take

Let best(i) be the most you can take from houses 0 through i. Skip house i and you keep best(i - 1). Rob it and house i - 1 is off limits, so you get best(i - 2) + nums[i]:

best(i) = max(best(i - 1), best(i - 2) + nums[i])

At the house with 9, skipping keeps 7 and robbing gives 2 + 9 = 11. Rob it.

Add nums[i] to best(i - 2).

The house next door is left out.

Rolling the DP

The recurrence only looks two houses back, so you don't need the whole table. twoBack and oneBack hold the best totals so far, not house values.

python
twoBack, oneBack = 0, 0
for money in nums:
    current = max(oneBack, twoBack + money)
    twoBack, oneBack = oneBack, current
return oneBack

Compute current before you shift, or you overwrite a total you still need.

ApproachTimeExtra spaceTrade-off
Full DP arrayO(n)O(n)Every prefix on show
Rolling variablesO(n)O(1)Keeps only the two totals needed

Walkthrough

Run it on [2, 7, 9, 3, 1].

The best totals go 2, 7, 11, 11, 12. At the 3, robbing gives 7 + 3 = 10, less than the 11 you already have, so you skip it. At the 1, robbing gives 11 + 1 = 12.

The answer is 12: houses 0, 2 and 4, holding 2, 9 and 1.

Checkpoint · predict the next step

Step 3 of 7 on the stage: House 1 has 7. Skip it and keep oneBack = 2, or take it: twoBack + 7 = 0 + 7 = 7. Take it: best = 7.

best = [2, 7, ·, ·, ·]

What does step 4 show?
Step through it on the stage

Pitfalls

  • Taking every other house fails. For [5, 1, 1, 5], every other house gives 6 either way, but the first and last give 10.
  • Grabbing the bigger of two neighbors can block a better pair later.
  • Robbing a house adds to best(i - 2), a total, not to nums[i - 2].
  • An empty street gives 0, and one house gives its own value.

What's the most you can take from [5, 1, 1, 5]?

Complexity

Each house gets one addition and one comparison: O(n) time. You keep two totals and a temporary, so extra space is O(1).

Every house has to be read, so no solution beats O(n).

Rolling DP

Time
O(n)
Space
O(1)
Where the time goes
  • Scan each house onceOne recurrence step per house.dominantO(n)
  • Compare skip and takeOne addition and one max.O(1)
  • Rolling stateTwo totals and a temporary.O(1)
How it grows
input size n →opsO(n²)O(n log n)O(n)O(log n)O(1)
Roughly what that costs
n101001,00010,000
O(n)101001K10K

As fast as reading the input, in constant memory.

In short

Define best(i) = max(best(i−1), best(i−2) + nums[i]) — skip this house, or take it and whatever was optimal two houses back. Roll two variables forward for O(1) space. The recurrence enforces the no-adjacent constraint automatically.

TimeO(n)SpaceO(1)

Common mistake

Greedily taking all even or all odd houses — the optimal choice depends on values, not parity.

NextClimbing Stairs →Ways to reach step n = ways to reach n−1 plus n−2.

Related problems

Climbing StairsEasyCoin ChangeMedium