Skip to content
APPLIED CODING YouTube

Applied Coding › Guides › Dynamic Programming

Dynamic programming, discovered — the house robber

Five houses, one alarm rule, and a question that turns an exploding tree of choices into a single walk down the street. No formula to memorize: by the end you will have invented it.

Pattern: Dynamic programming · Language: Python · Reading time ≈ 15 min · Video ≈ 9 min
The video's thumbnail: “Take the $9?” — he reaches for the $9 house while the alarm wire to the $8 house next door beeps

Watch the video version

The same story in nine minutes, with the street, the alarm, the tree and the cart in motion. The written version below goes slower and keeps the code in one place.

Watch on YouTube

1 · The problemThe street and the rule

A street of five houses. Every house has cash inside: $2, $7, $9, $8 and $1, in that order. Every pair of neighbours is wired together, and if you rob two houses right next to each other, the alarm goes off.

You may rob as many houses as you like, as long as no two of them are neighbours. The goal: walk away with as much money as possible.

The five houses with $2, $7, $9, $8 and $1 on their signs, joined by a red alarm wire; the narrator stands at the first house
The street. The red wire is the rule: two neighbours together, and the alarm rings.

Nothing about this looks hard. It is five numbers. That is exactly why it is a good place to meet dynamic programming: the problem is small enough to hold in your head, and the obvious ideas still fail.

2 · The obvious ideaTake the biggest house

The first instinct is the natural one: go for the richest house. The $9 house gives nine dollars, so take it.

But the moment you do, both of its neighbours are off limits. The $7 and the $8 next door are gone. Of what is left, the biggest is the $2, then the $1.

The narrator at the $9 house, a rain cloud in his thought bubble; the $7 and $8 houses on either side are shaded red with red pointers over them
One grab, two houses locked. The $9 looks great by itself and costs you the two best neighbours on the street.
$2
taken
$7
blocked
$9
taken
$8
blocked
$1
taken

9 + 2 + 1 = $12

Now look at the plan that skips the $9 entirely: take the $7 and the $8. They are not neighbours — the $9 sits between them — so the alarm stays quiet, and the total is $15.

The $7 and $8 houses lit green with the $9 between them; above the street, 9 + 2 + 1 = 12 greyed out and 7 + 8 = 15 in green
$7 + $8 = $15 beats everything the $9 can be part of. A smaller choice now can give a much bigger result later.

This is the problem with "always take the biggest": a local choice has consequences two houses away, and the choice itself knows nothing about them. The approach is called greedy, and here it is simply wrong.

3 · Brute forceFine, try everything

If you can't make the right choice immediately, try every choice. At every house there are two options: rob it or skip it. Make both choices at the first house, both again at the second, and so on. Every full sequence of rob and skip decisions is one possible plan.

A binary tree five levels deep, each node marked R for rob or S for skip, with branches that rob two neighbours cut off
Every path from the top to the bottom is a plan. Branches that rob two neighbours in a row trip the alarm and are cut.

With five houses that is 2 × 2 × 2 × 2 × 2 = 32 sequences. Throw away the ones that rob two neighbours and 13 legal plans remain. You could check all of them by hand and find the $15.

Now imagine a street of a hundred houses. The tree does not grow a little; it explodes. 2100 is a number with 31 digits:

1 267 650 600 228 229 401 496 703 205 376

A card reading 100 HOUSES above a 31-digit count of sequences; the narrator stands beside a tree that fills the frame
Five houses you can survive. A hundred, you cannot — not by trying every plan.

The tree is honest, at least: somewhere inside it is the best plan. The problem is that we are solving the same little problem again and again, in different branches, without noticing.

4 · The observationTwo paths, one house

Look at two different branches of that tree. One robs the first house and skips the next two: it reaches the fourth house carrying $2. Another skips the first, robs the second, skips the third: it reaches the same fourth house carrying $7.

The whole street with the $8 house lit and the narrator in front of it; two piles of cash on the pavement under it, $2 and $7, the $7 pile highlighted
Two histories arrive at the same house. From here on, their futures are identical — the only thing that differs is what they are carrying.

Now ask the question that cracks the problem open: standing at this house, do I need to remember every decision that got me here?

No. From this house onward, both histories face exactly the same street and exactly the same rule. Whatever the best thing to do next is, it is the same for both of them. The only thing that matters is how much money each one brought. One brought $7, the other brought $2 — so the $2 history can be thrown away. Not because it was wrong, but because the $7 history can do everything it can do, with more money.

The key idea

The exact path that produced the $2 no longer matters. At every position, keep only the best result found so far. Everything else about the past is noise.

5 · The stateThe question changes

This changes what we are asking. Instead of "which houses did I rob?" — a question about a whole history — we ask a question about a position:

What is the most money I can have after considering this house?

We will store that answer for every house. Call it dp[i]: the most money you can have after considering the first i + 1 houses (house 0 through house i, counting from zero as the code will). Instead of remembering an enormous tree, we keep one useful number at each position.

The five houses with an empty box under each, labelled dp[0] to dp[4]; above them the definition: dp[i] = most money up to house i
One box under each house. Each will hold one number: the best total possible after that house.

That number — the one piece of information you need about the past — is what dynamic programming calls the state. Finding it is the whole game. The rest of this guide is what happens once you have it.

6 · Building itHouse by house

The first house is easy. There is $2 inside and nothing before it, so the best you can have after it is $2. dp[0] = 2.

The second house gives you a choice. Skip it and keep what you had: $2. Or rob it: $7 — but then the first house must be left alone, so $7 is all you get. Seven wins. dp[1] = 7.

The third house, the $9, has the same two choices, and now the second one has a twist. Skip it and keep the best so far: $7. Or rob it — but robbing it means the $7 next door is forbidden, so you cannot add $9 to $7. What can you add it to? The best total from two houses back, where nothing conflicts: $2. So robbing gives 2 + 9 = $11. Eleven beats seven. dp[2] = 11.

A balance scale labelled MAX with a SKIP card showing 7 on one pan, above the street where the narrator points at the $9 house
At every house the same weighing: skip it and keep the previous best, or rob it and add its cash to the best from two houses back.

Notice that nothing about the third house needed the tree. It needed two numbers from the boxes before it, and one weighing.

7 · The recurrenceThe rule that repeats

By the third house the pattern is already clear, and it is the same at every house after it:

  • If I skip this house, my best total is whatever it was at the previous house: dp[i - 1].
  • If I rob this house, the previous house is off limits, so I take the best total from two houses back and add this house's cash: dp[i - 2] + money[i].
  • Whichever is bigger is the answer for this house.

dp[i] = max( dp[i - 1], dp[i - 2] + money[i] )

This one line is the whole idea. The blue term is "skip"; the green term is "rob". A rule like this, that defines an answer in terms of smaller answers of the same kind, is called a recurrence. You did not look it up. You found it by standing at the third house and asking what you were allowed to add the $9 to.

8 · The runWalking the whole street

Apply the rule from the first house to the last. Every row below is one weighing.

HouseCashSkip: keep dp[i−1]Rob: dp[i−2] + cashWinnerdp[i]
1$200 + 2 = 2rob2
2$720 + 7 = 7rob7
3$972 + 9 = 11rob11
4$8117 + 8 = 15rob15
5$11511 + 1 = 12skip15

The last box holds the answer: $15, the most money anyone can take from this street without ringing the alarm. Five weighings instead of 32 plans.

$7 + $8 = $15 in green above the street, 9 + 2 + 1 = 12 crossed in red; the $7 and $8 houses glow, the $9 is shaded; the dp boxes read 2, 7, 11, 15, 15
The boxes after the walk: 2, 7, 11, 15, 15. The greedy $12 never stood a chance.

Which houses, though?

The boxes tell you how much, and they also tell you which houses, if you read them backwards. Start at the last box. At house 5, dp[4] equals dp[3], so robbing house 5 did not help: it was skipped. At house 4, dp[3] is bigger than dp[2], so house 4 was robbed — jump back two, past its forbidden neighbour, to house 2. There dp[1] is bigger than dp[0]: house 2 was robbed too. The plan is houses 2 and 4: $7 + $8. Exactly the pair the greedy grab locked out.

Did we lose anything?

Every one of the 13 legal plans is still accounted for. Each weighing kept the better of two totals, and a total that lost at some house could never have beaten the winner later — the future was identical for both. The tree was not ignored; it was compressed, one number per house.

9 · The nameThis is dynamic programming

Only now does the idea deserve its name. Dynamic programming means: solve smaller versions of the problem, remember their answers, and use them to build the next answer instead of solving the same thing again.

A yellow title card DYNAMIC PROGRAMMING with three chips: SMALLER PROBLEM, REMEMBER ANSWER, BUILD BIGGER PROBLEM, above the full street with every dp box filled
Smaller problem, remember the answer, build the bigger problem. The whole technique in three chips.

Here the smaller problems were literally shorter streets: the best total for the first house, then the first two, then the first three. Each answer was remembered in a box, and each new box was built from the two before it. "Programming" in the name has nothing to do with code — it is an old word for planning in a table. The table of boxes is the program.

The thing to carry away is not the word. It is the move that made it possible: realizing that an enormous number of histories could be summarized by a small amount of information, and that once you knew the best result so far, you did not need to remember how you got there.

10 · The codeTranslate what we did into Python

The code is a transcript of the walk. One slot for the answer at every house, the first two filled by hand, and the weighing in a loop for the rest.

def rob(nums):    if not nums:        return 0     if len(nums) == 1:        return nums[0]     dp = [0] * len(nums)     dp[0] = nums[0]    dp[1] = max(nums[0], nums[1])     for i in range(2, len(nums)):        dp[i] = max(            dp[i - 1],            dp[i - 2] + nums[i]        )     return dp[-1]

Reading it against the story:

  • nums is the street: the cash in each house, in order. Our street is [2, 7, 9, 8, 1].
  • The two ifs handle streets too short to have a "two houses back": no houses means $0, one house means take it.
  • dp = [0] * len(nums) is the row of empty boxes.
  • dp[0] = nums[0] is the first house: its money is the best you can have. dp[1] = max(nums[0], nums[1]) is the second: the larger of the first two, because you cannot have both.
  • From the third house on, every house follows the same rule, so a loop does the rest. The highlighted line is the recurrence, word for word: dp[i - 1] is skipping, dp[i - 2] + nums[i] is robbing, max is the weighing.
  • dp[-1], the last box, is the answer.
A code editor over the street showing the loop and the dp line, dp[i - 1] highlighted, while the narrator points at the $9 house; the SKIP card reads dp[i - 1]
Every line of the loop is something that happened on the street. If a line has no physical meaning to you, you are memorizing, not understanding.

For our street the array ends up as [2, 7, 11, 15, 15] — the same five boxes as the table, because it is the same five weighings. Do not think of this array as a collection of numbers that happened to come out of a formula. Every entry has a meaning: the most money I can have after considering this house.

How much work is this?

One pass over the street, one weighing per house: the time grows in proportion to the number of houses, O(n). A hundred houses is a hundred weighings, not a 31-digit number of plans. The array of boxes is also one slot per house, so the extra memory is O(n) as well. That second number is about to shrink.

11 · Less memoryOnly two values

Look at the formula once more. To fill the box at house i, which boxes did we read? Only dp[i - 1] and dp[i - 2]. Never the whole array. Never a box three houses back. So why store all of them?

Keep just the two answers the next house actually needs. Call them prev1 (the previous house's best) and prev2 (the one before that). At every house, compute the current best from those two, then shift them forward: the old prev1 becomes prev2, the current answer becomes prev1.

The narrator pushes a two-slot cart labelled prev2 and prev1, holding 11 and 15, past the last house of the street; a card labelled current floats above it
A cart with two slots is all the memory the street needs. Roll it past each house, weigh, shift, roll on.
def rob(nums):    prev2 = 0    prev1 = 0     for money in nums:        current = max(            prev1,            prev2 + money        )         prev2 = prev1        prev1 = current     return prev1

Read it the same way: prev1 is my best if I skip this house, prev2 + money is my best if I rob it, current is the larger, and then the cart rolls forward. Starting both values at 0 even makes the short-street cases disappear: with no houses the loop never runs and the answer is 0; with one house, max(0, 0 + money) is its money.

HouseCashprev2prev1current = max(prev1, prev2 + cash)
1$200max(0, 0 + 2) = 2
2$702max(2, 0 + 7) = 7
3$927max(7, 2 + 9) = 11
4$8711max(11, 7 + 8) = 15
5$11115max(15, 11 + 1) = 15

Same answers, same order, and the memory no longer grows with the street: two variables whatever its length, O(1) extra space. The time is still one weighing per house, O(n).

A fair trade-off

The two-variable version forgets the boxes, so it can no longer tell you which houses to rob — only how much. When you need the plan itself, keep the array. Knowing what each version remembers is part of understanding it.

12 · The lessonThree questions for any problem like this

The important part of this problem is not the formula. Formulas are what you end up with; they are not where you start. The important part is the move in section 4: the huge number of possible histories could be summarized by a small amount of information. Once you knew the best result so far, you did not need to remember every way you got there.

So when you meet a new problem that smells like this one — choices, a constraint between them, a best total — do not reach for a recurrence. Ask three things, in order:

  1. What is my state?

    What is the smallest description of "where I am" that still lets me decide what to do next? Here: the house I am considering, and the best total possible after it.

  2. What choices can I make?

    At that state, what are my options? Here: rob this house, or skip it.

  3. Which smaller states do I need to decide?

    Which earlier answers does each choice depend on? Here: skipping needs the previous house's answer; robbing needs the one from two houses back.

Three cards: WHAT IS THE STATE? answered HOUSE i, WHAT CHOICES DO I HAVE? answered ROB / SKIP, WHAT PREVIOUS STATES DO I NEED? — under a HOUSE ROBBER title
State → choices → previous states. Answer these and the recurrence writes itself; the code is mostly translation.

Answer those three and the recurrence is not something you remember, it is something you read off your own answers. The code, as you saw, is mostly translating that reasoning line by line.

Before you write a line

Try the three questions on the street yourself, from memory, without looking up. If you can say what the state is in one sentence, you have the hard part. Then write the code.

13 · Try itTry your own street

Change the cash, watch the boxes

Type any amounts. The greedy grab and the dynamic-programming walk are both computed live — see how often "take the biggest" loses, and read the plan back from the boxes.

14 · PracticeFour problems, same shape

None of these say "dynamic programming" on the tin. For each, answer the three questions before you write anything. If your state is right, the code is short.

  • Warm-upClimbing stairs

    A staircase of n steps; you climb 1 or 2 at a time. How many distinct ways to reach the top? The state is "which step am I on"; the two choices are the step sizes. Notice how the previous-states answer rhymes with the street.

  • PracticeThe house robber, from scratch

    Close this page and write both versions — the array and the two variables — for a street given as a list of amounts. Then test them on a street where greedy wins, and one where it loses.

  • VariationMin-cost climbing stairs

    Every step has a toll you pay to stand on it; you may start on step 0 or step 1 and climb 1 or 2 at a time. What is the cheapest way to the top? Same state, same choices — but now you are minimizing, and the "cash" is a cost.

  • ChallengeDelete and earn

    From a list of numbers, pick one, earn its value, and every copy of its neighbours in value (one less, one more) is deleted; repeat. Maximize what you earn. It looks nothing like a street. Find the street inside it.

A board showing the five houses arranged in a ring, the alarm wire joining the last house back to the first

Next: the street becomes a circle

What if the first and the last house are neighbours too? Now choosing the first house can affect a decision all the way at the end. The core idea still works — but the state needs rethinking. That is the next guide.

Don't memorize the table. Learn how to discover it.