The idea: each answer needs only the last two

Many dynamic programming problems fill a single row of cells, dp[0], dp[1], …, dp[n], from left to right. In the two problems on this page each cell looks back only one or two cells: dp[k] is built from dp[k-1] and dp[k-2]. The animation draws the arrow from k-1 in blue under the row and the arrow from k-2 in green over it.

Houses 1 to 5 hold 2, 7, 9, 3, 1. The dp row reads 0, 2, 7, then dp[3] gets a green arrow from dp[1] (rob house 3: 2 + 9 = 11) and a blue arrow from dp[2] (skip house 3: 7); dp[3] = max(7, 11) = 11
Cell k has only two choices: come from k−1 (blue) or from k−2 (green). Nothing further back is needed.

Climbing stairs

You climb a staircase of n steps, 1 or 2 steps per move. How many different ways are there to reach the top? Look at the last move. It was either a 1-step move from step k−1 or a 2-step move from step k−2, and those two groups of ways do not overlap, so they add:

ways[0] = 1                         (standing on the ground is one way)
ways[k] = ways[k-1] + ways[k-2]     (a missing ways[-1] counts as 0, so ways[1] = 1)

The row is 1, 1, 2, 3, 5, 8, 13, …: the Fibonacci numbers. For 6 steps there are 13 ways (Demo: climbing stairs, n = 6); for 10 steps, 89.

House robber

Houses on a street hold v[1], …, v[n]. A robber wants the most money, but robbing two neighbouring houses sets off the alarm. Let dp[k] be the most money from houses 1..k. For house k there are two choices:

  • Skip it: the best is still dp[k-1].
  • Rob it: house k−1 must be left alone, so add v[k] to the best up to k−2.
dp[0] = 0
dp[k] = max( dp[k-1],  dp[k-2] + v[k] )      (dp[-1] counts as 0, so dp[1] = v[1])

For 2 7 9 3 1 the row is 0, 2, 7, 11, 11, 12, so the answer is 12 (Demo: house robber 2 7 9 3 1). Climbing stairs adds the two options; house robber takes the larger one. The shape of the work is the same.

Which houses? The trace back

The last cell gives the amount, not the houses. Walk back from dp[n]: if dp[k] = dp[k-1], house k was skipped, so move one cell left. Otherwise house k was robbed, so move two cells left. For 2 7 9 3 1: dp[5] = 12 ≠ 11 (rob 5), dp[3] = 11 ≠ 7 (rob 3), dp[1] = 2 ≠ 0 (rob 1): houses 1, 3, 5, worth 2 + 9 + 1 = 12.

Why greedy fails

A tempting rule is "rob the richest house still allowed, then repeat". On 4 5 4 1 5 it robs house 2 (5), which rules out houses 1 and 3, then house 5 (5): 10 in total. The DP finds 4 + 4 + 5 = 13 (Demo: greedy fails on 4 5 4 1 5). Another rule, "all odd houses or all even houses", fails on 2 1 1 2: it gets 3, but houses 1 and 4 give 4.

Street 4 5 4 1 5. Greedy robs houses 2 and 5 for 5 + 5 = 10, marked wrong. DP robs houses 1, 3 and 5 for 4 + 4 + 5 = 13, marked right
Robbing the richest house first blocks two neighbours that are worth more together.

Circular street

If the houses stand in a circle, house n is next to house 1, so they can't both be robbed. At least one of them is left alone, so solve two straight streets and take the better: A = houses 1..n−1 (leave out the last) and B = houses 2..n (leave out the first). For 2 7 9 3 1, A gives 11 (houses 1, 3) and B gives 10 (houses 2, 4), so the answer is 11, not the straight street's 12 (Demo: circular street 2 7 9 3 1).

Pass A leaves out house 5 and robs houses 1 and 3 of 2 7 9 3 for 11. Pass B leaves out house 1 and robs houses 2 and 4 of 7 9 3 1 for 10. The circular answer is max(11, 10) = 11
A circle becomes two straight streets, each missing one end; the answer is the better of the two.

Time and space

MethodTimeSpace
Plain recursion f(k) = f(k-1) + f(k-2)exponential (about 1.6n calls)O(n) stack
The dp row (this page)O(n)O(n)
Two variables prev2, prev1O(n)O(1), but no trace back

Because each cell reads only the two before it, you can keep just two numbers and slide them along. The full row is only needed to recover which houses were robbed.

See also: the recursion tree and memoization for the same recurrence are on Fibonacci with dynamic programming and Memoization vs Tabulation. Two-dimensional tables with a trace back are on 0/1 Knapsack and Coin Change, and Longest Increasing Subsequence looks back at every earlier cell, not just two.

The same choice on a tree, where each node keeps two answers (taken and not taken) and combines its children's answers bottom-up, is on DP on Trees.

The same skip-or-take row, with the "take" arrow jumping back to the last compatible job instead of two cells, is on Weighted Interval Scheduling.

When each day needs more than one number, see Stock Trading State Machine DP, where hold, sold and rest each get a cell per day.

What the page leaves out

Stairs with other step sizes (1, 2 or 3 steps, or a set of allowed sizes) and stairs with a cost per step ("min cost climbing stairs"); the recursion tree and memoized top-down version; house robber on a tree ("House Robber III"), where each node returns two values; huge n, where Fibonacci-style counts are taken modulo a prime or computed with matrix powers in O(log n).