House Robber

The problem: a street of houses, each holding some amount of money. You can rob any set of them, with one rule — rob two adjacent houses and the alarm goes off. What is the most money you can take?

Climbing stairs asked how many. This one asks which is best — and that single change turns a counting problem into an optimization problem. Six beats, each unlocked by the one before: rob the street by hand, find the one question that splits every haul, follow the recursion, add memory, build the table bottom-up, then carry the idea to a circle and a minimum.

1

Play the game

Rob the richest set of houses on a 6-house street without ever taking two in a row.

This haul: nothing selected

Hauls you've bankedbest 0 / 19

Pick some houses and bank the haul. It lands here.

Discover the rule

Every haul answers one yes/no question. That question is the recurrence.

One question, asked once

Every legal haul either robs house 5 or it doesn't. There is no third option. Sort your hauls by that one question and watch what each pile is worth.

Hauls to sort0 / 6 sorted

houses 0, 2, 5 = 19

houses 0, 2, 4 = 12

houses 0 = 2

houses 0, 2 = 11

houses 0, 3 = 5

houses 0, 3, 5 = 13

Skips house 5

These never touch the last house, so the best of them is exactly the answer for houses 0..4.

Empty so far.

Robs house 5

Robbing house 5 rules out house 4, so the rest must come from houses 0..3.

Empty so far.

Finish beat 1 to unlock

Follow recursion

Run the rule as function calls and find the work being redone.

Recurrence

The rule says what an answer depends on:

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

Recursion

The code follows that rule by calling itself until it reaches rob(0) or rob(1), the two hauls you can read straight off the street.

function rob(i, nums) {
  if (i === 0) return nums[0];
  if (i === 1) return Math.max(nums[0], nums[1]);
  return Math.max(
    rob(i - 1, nums),
    nums[i] + rob(i - 2, nums));
}

Run the recursive code for rob(5). Tap a yellow call to reveal the calls it makes. Keep going until the tree is complete.

1 / 15 calls

Finish beat 2 to unlock

Add memory

Decide when the cache already holds the answer.

Same recursion, one new ingredient

Recursion still starts at rob(6) and asks about smaller stretches of the street. This time it carries a cache, so an answer can be saved once and reused.

Current call stack

rob(6)rob(5)rob(4)rob(3)rob(2)

Top-down means we began with rob(6) and followed its smaller dependencies.

Cache

rob(0)

2

rob(1)

7

rob(2)

?

rob(3)

?

rob(4)

?

rob(5)

?

rob(6)

?

The base cases start filled because their answers are already defined.

Decision 1 of 3

Recursion requests rob(2). What should it do?

rob(2) is not cached

Finish beat 3 to unlock

Build bottom-up

Fill the same table in order, and confirm the number you predicted.

New task: build the same answers without recursive calls

Memoization is top-down

Start at the far end of the street and recurse back toward house 0, saving answers as they return.

Tabulation is bottom-up

Start at house 0 and fill each answer once its two dependencies exist.

Both store the same meaning: the most loot obtainable from houses 0..i. Only the order changes.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Before you fill: two starting facts

Given base cases

dp[0] = 2

One house available, no adjacency to worry about. Take it.

dp[1] = max(2, 7) = 7

Houses 0 and 1 are next door, so you take the richer one and never both.

From dp[2] onward, every cell is the max of two options — and that is the cell the table will stop and ask you for.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

2

7

11

12

19

22

rob.ts

1function rob(nums) {
2 const dp = [nums[0]];
3 dp[1] = Math.max(nums[0], nums[1]);
4 for (let i = 2; i < nums.length; i++) {
5 dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
6 }
7 return dp[nums.length - 1];
8}

Base caseComputedWinning optionAnswer / dependency arrow

Finish beat 4 to unlock

Make it transfer

A circle, a minimum, a looser constraint. Same derivation each time.

Variation 1: the houses are now in a circle, so house 0 and the last house are adjacent too. What's the cleanest fix?

Variation 2: same street, but now you want the MINIMUM loot while still robbing at least one house in every window of three. What changes?

Variation 3: you may skip at most two houses in a row (so no three consecutive skips). Which predecessors does dp[i] need?

Final check: climbing stairs added its two buckets; house robber takes the max of them. Why the difference?

Finish beat 5 to unlock

The pattern, formally

The state: dp[i] is the most money obtainable from houses 0..i. The recurrence: house i is either skipped, leaving dp[i-1], or robbed, which forbids house i-1 and leaves nums[i] + dp[i-2]. So dp[i] = max(dp[i-1], nums[i] + dp[i-2]) with dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). The dependency shape is identical to climbing stairs; only the combine step differs, because this problem chooses instead of counting.

Naive recursion

Start at the last house, branch on skip vs rob, store nothing.

O(2ⁿ) time

O(n) call stack

Memoization

Same branching, but each index is resolved once and cached.

O(n) time

O(n) cache plus call stack

Tabulation

Walk the street once, one comparison per house.

O(n) time

O(n) table, reducible to O(1)

Takeaways

One question — does this haul take the last house? — splits every possibility into two groups. That split IS the recurrence.
Counting problems add their buckets. Optimization problems take the best bucket. The partition is the same move either way.
Robbing house i forbids house i-1, which is why the second term reaches back to dp[i-2] rather than dp[i-1].
Greedy fails here: taking the largest house first can cost you two neighbours worth more together. The table considers both futures.
The dependency graph matches climbing stairs exactly, so recursion wastes work in exactly the same way, and the same two fixes apply.
Space drops to O(1) once you notice only dp[i-1] and dp[i-2] are ever read.