Tabulation (bottom-up DP) — iterative: Worked examples

This is the "roll up your sleeves" companion to the parent Tabulation note. There we learned the 5-step recipe (State, Recurrence, Base, Order, Answer). Here we stress-test it against every kind of case a tabulation problem can hand you — including the ugly ones the parent note only hinted at.

Before we begin, one promise: every symbol is earned. dp[i] just means "the answer we stored in box number $i$ of a list of boxes." A table is that list of boxes. Nothing more mysterious than a row of labelled shoeboxes on a shelf.

The scenario matrix

Think of a tabulation problem as a machine. What kinds of inputs can jam it? Here is the full menu of "case classes" — every worked example below is tagged with the cell(s) it covers.

Cell	Case class	What makes it tricky	Covered by
C1	1D table, additive recurrence	the easy baseline	Ex 1
C2	Degenerate / tiny input ( $n = 0$ , empty set)	base case is the whole answer	Ex 2
C3	2D table, binary "take/skip" choice	two dependencies from previous row	Ex 3
C4	Impossible / "no solution" state	must represent $\infty$ or $- 1$ safely	Ex 4 (Coin Change)
C5	Order matters — wrong loop direction breaks it	high→low vs low→high	Ex 5
C6	Two strings, 2D grid, match-vs-mismatch	diagonal dependency	Ex 6 (LCS)
C7	Real-world word problem	translating English → state	Ex 7
C8	Exam twist: a "trap" recurrence	the obvious recurrence is wrong	Ex 8

We will hit all eight cells in eight examples. Let's go.

Ex 1 — C1: the additive baseline (Tribonacci)

Forecast: guess whether $T (6)$ is closer to 10 or to 25 before reading on.

State. dp[i] = the $i$ -th Tribonacci number. Why this step? We always name the box first so the recurrence has something concrete to fill.
Recurrence. dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Why this step? The definition literally sums the three predecessors — that IS the optimal substructure.
Base cases. dp[0]=0, dp[1]=1, dp[2]=1. Why this step? At $i = 2$ the recurrence would read dp[-1], which doesn't exist. We must seed enough boxes to cover the deepest reach-back (here, 3 boxes).
Order. Increasing $i$ . Why this step? When we fill dp[i], all of dp[i-1], dp[i-2], dp[i-3] are already written.
Answer. dp[6].

Filling the shelf left to right — I write out each new box in words so nothing is hidden inside a loop:

dp[3] $= d p [2] + d p [1] + d p [0] = 1 + 1 + 0 = 2$ .
dp[4] $= d p [3] + d p [2] + d p [1] = 2 + 1 + 1 = 4$ .
dp[5] $= d p [4] + d p [3] + d p [2] = 4 + 2 + 1 = 7$ .
dp[6] $= d p [5] + d p [4] + d p [3] = 7 + 4 + 2 = 13$ .

i	0	1	2	3	4	5	6
dp[i]	0	1	1	2	4	7	13

Verify: the sum of any window of 3 consecutive earlier boxes gives the next — e.g. $d p [6] = d p [5] + d p [4] + d p [3] = 7 + 4 + 2 = 13$ . ✅ Answer 13 (closer to 10 — did your forecast hold?).

Ex 2 — C2: the degenerate input

Forecast: zero stairs — is the answer 0 ways, or 1 way?

State. dp[i] = number of distinct ways to reach step $i$ . Why this step? We must decide what "reaching step 0" means before answering.
Base case reasoning. There is exactly one way to "climb zero stairs": do nothing. That empty sequence of moves is a valid way. Why this step? The most common bug here is writing dp[0]=0. But 0 would say "impossible," which is false — standing still is a way.
No recurrence runs. For $n = 0$ the loop that would fill dp[2], dp[3], … never starts (there is nothing between index 2 and index 0). So the answer is read straight from the base cell — this is exactly the case where the base case is the whole answer.
Answer. dp[0] = 1.

Verify: $d p [0] = 1$ ; and downstream $d p [2] = d p [1] + d p [0] = 2$ (the two real ways: 1,1 and 2). ✅ Answer 1 way.

Ex 3 — C3: 2D take/skip (0-1 Knapsack full trace)

Forecast: can we do better than value 5?

First, the notation — every symbol defined before use:

We build a grid: rows = "first $i$ items available", columns = "capacity $c$ from 0 to 4". dp[i][c] = best value using the first $i$ items with capacity $c$ .

The recurrence (from the parent note), now that $w_{i}, v_{i}, c$ are all defined: $d p [i] [c] = {d p [i - 1] [c] max (d p [i - 1] [c], v_{i} + d p [i - 1] [c - w_{i}]) w_{i} > c w_{i} \leq c$

Why two dependencies from the previous row? Because item $i$ is either out (copy the row above at the same $c$ ) or in (its value $v_{i}$ plus the best packing of the earlier items into the leftover capacity $c - w_{i}$ — also from the row above).

The figure below shows exactly these two arrows. Read it like this: the yellow cell (bottom, pink ?) is dp[i][c] we are computing. The blue arrow straight down from the row above is the "skip" choice — it copies dp[i-1][c]. The pink diagonal arrow comes from dp[i-1][c-w_i] further left (leftover capacity after paying $w_{i}$ ) and represents the "take" choice, to which we add $v_{i}$ . We keep whichever is bigger.

Figure — Tabulation (bottom-up DP) — iterative

Row 0 (no items) = all zeros — with zero items available you can never earn value, whatever the capacity. Now fill each cell in words:

Row 1, item $(w_{1} = 1, v_{1} = 1)$ . For every $c \geq 1$ : skip = 0, take = $1 + d p [0] [c - 1] = 1 + 0 = 1$ . So dp[1][1..4] all become 1; dp[1][0]=0 (can't fit even weight 1).
Row 2, item $(w_{2} = 3, v_{2} = 4)$ . dp[2][0]=dp[2][1]=dp[2][2]= copy row 1 (weight 3 doesn't fit) $= 0, 1, 1$ . dp[2][3]: skip $= 1$ , take $= 4 + d p [1] [0] = 4$ ; max $= 4$ . dp[2][4]: skip $= d p [1] [4] = 1$ , take $= 4 + d p [1] [4 - 3] = 4 + d p [1] [1] = 4 + 1 = 5$ ; max $= 5$ .
Row 3, item $(w_{3} = 4, v_{3} = 5)$ . Cells $c < 4$ copy row 2. dp[3][4]: skip $= d p [2] [4] = 5$ , take $= 5 + d p [2] [0] = 5 + 0 = 5$ ; max $= 5$ (a tie — item 3 alone equals items 1+2).

$i \ c$	1	2	3	4
0 (none)	0	0	0	0
1 (1,1)	1	1	1	1
2 (3,4)	1	1	4	5
3 (4,5)	1	1	4	5

Order. Rows increasing. Why this step? Every read hits row $i - 1$ , which is finished.
Answer. Bottom-right cell dp[3][4] = 5.

Verify: enumerate all subsets fitting $W = 4$ : {} →0, {1}→1, {2}→4, {3}→5, {1,2}: w=4,v=5 ✓, {1,3}: w=5 ✗, {2,3}: w=7 ✗, {1,2,3}: w=8 ✗. Best feasible value = 5. ✅

Ex 4 — C4: the "impossible" state (Coin Change — minimum coins)

Forecast: greedy would grab a 4, then need 2 → 4+1+1 = three coins. Can we beat that?

Here the table can hold an impossible entry — some amounts might be unmakeable. We need a value that means "no solution" and survives the min.

Definition The infinity sentinel — how to actually store it

A sentinel is a stand-in value that means "no answer here yet." For a minimisation table we want it to be larger than any real answer, so min(real, sentinel) always keeps the real one. Two safe ways to write it in code:

Use language infinity: INF = float('inf') in Python. Then 1 + INF is still INF, so impossible paths never win a min.
Use a big constant: INF = amount + 1 (any value strictly bigger than the largest possible coin count, since you can never need more than amount coins of value 1). Guard against overflow by checking if dp[a-c] != INF before adding 1, or simply cap the value.

Never use $- 1$ as the sentinel inside the min — it looks smaller than every real answer and would corrupt the result. If you want $- 1$ to signal "impossible", only convert to it after the table is finished (return dp[amount] if dp[amount] != INF else -1).

State. dp[a] = fewest coins summing to amount $a$ . Why this step? One box per amount from 0 up to the target.
Sentinel initialisation. Initialise every dp[a] to INF (as defined above), except dp[0]=0. Why this step? INF means "not yet reachable." Because we take a min, an unreachable path never wins.
Recurrence. For each amount $a$ and coin $c \leq a$ : $d p [a] = min (d p [a], 1 + d p [a - c]) .$ Why this step? Using one coin $c$ leaves a smaller subproblem $a - c$ ; add 1 for the coin we just spent. If $d p [a - c]$ is still INF, then $1 + INF$ stays effectively INF and loses the min — impossibility propagates safely.
Order. $a$ from 1 up to target. Why this step? $d p [a - c]$ has a smaller amount, already finalised.
Answer. dp[target], or "impossible" (convert to $- 1$ ) if it's still INF.

Filling in words (coins ${1, 3, 4}$ ):

dp[1]: only coin 1 fits → $1 + d p [0] = 1$ .
dp[2]: only coin 1 fits → $1 + d p [1] = 2$ .
dp[3]: coin 1 → $1 + d p [2] = 3$ ; coin 3 → $1 + d p [0] = 1$ ; min $= 1$ .
dp[4]: coin 1 → $1 + d p [3] = 2$ ; coin 3 → $1 + d p [1] = 2$ ; coin 4 → $1 + d p [0] = 1$ ; min $= 1$ .
dp[5]: coin 1 → $1 + d p [4] = 2$ ; coin 3 → $1 + d p [2] = 3$ ; coin 4 → $1 + d p [1] = 2$ ; min $= 2$ .
dp[6]: coin 1 → $1 + d p [5] = 3$ ; coin 3 → $1 + d p [3] = 2$ ; coin 4 → $1 + d p [2] = 3$ ; min $= 2$ .

a	0	1	2	3	4	5	6
dp[a]	0	1	2	1	1	2	2

So dp[6] = 2 (coins $3 + 3$ ). Beats greedy's 3!

Impossible case: with coins ${3, 4}$ only, both dp[1] and dp[2] are never reached (no coin $\leq 2$ ), so they stay INF — amount 1 or 2 is genuinely unmakeable, and our sentinel reports that cleanly without corrupting any later min.

Verify: $6 = 3 + 3$ uses 2 coins; no single coin equals 6 and no coin pair beats 2, so minimum = 2. And with ${3, 4}$ , amount $2$ = impossible. ✅

Ex 5 — C5: order matters (1D space-optimised knapsack)

Forecast: if we loop capacity low→high instead, will the answer be too big or too small?

We keep only one row and update it in place. The recurrence becomes dp[c] = max(dp[c], v_i + dp[c-w_i]), using the same $w_{i}, v_{i}$ (weight/value of item $i$ ) defined in Ex 3. The subtlety: dp[c-w_i] must still mean the previous item's value, not this item's freshly-updated value (that would let us pick the same item twice — breaking 0/1). (See Space Optimization in DP.)

The figure makes the danger visible. The single row of cells is our dp[c] shelf, $c = 0..4$ . The yellow arrow at the top shows the safe sweep direction (high→low). When we update the yellow upd cell dp[4], the pink curved arrow shows it reading the blue old cell to its left — and because we sweep from the right, that left cell has not been overwritten yet this round, so it still holds the previous item's value. Sweep the other way and that left cell would already be this-round's value → the item gets reused.

Correct — loop $c$ high→low. When we write dp[4], the cell dp[4-w] to its left is still last-round's value because we haven't touched it yet this round. Why this step? High→low guarantees a read from a not-yet-overwritten (i.e. previous-row) cell.
Wrong — loop $c$ low→high. We'd update dp[1] first, then dp[2] might read the just-updated dp[1], effectively reusing an item.

Concrete failure with item $(1, 1)$ starting from zeros, low→high (I write each update in order): dp[1]=max(0,1+dp[0])=1, then dp[2]=max(0,1+dp[1])=2, then dp[3]=max(0,1+dp[2])=3, then dp[4]=max(0,1+dp[3])=4 — using item 1 four times! That's unbounded knapsack, not 0/1.

High→low on the full item list gives the correct 5 (matching Ex 3's dp[3][4]).

Verify: correct 1D high→low answer = 5 (equals the 2D result). The buggy low→high on a single item $(1, 1)$ with $W = 4$ yields 4 (wrong, item reused). ✅

Ex 6 — C6: two strings, diagonal dependency (LCS)

Forecast: guess the LCS length — 3, 4, or 5?

A subsequence keeps order but may skip letters. First, name the two strings so the recurrence is unambiguous:

The recurrence has a match case and a mismatch case: $d p [i] [j] = {d p [i - 1] [j - 1] + 1 max (d p [i - 1] [j], d p [i] [j - 1]) X_{i} = Y_{j} (match — extend the diagonal) X_{i} \neq = Y_{j} (drop one letter)$

The figure shows the three neighbours every cell depends on. The pink ? cell is dp[i][j]. On a match (yellow diagonal arrow) it copies the up-left cell dp[i-1][j-1] and adds 1 — the shared last letter caps a common subsequence, the rest lives in the strictly-smaller prefixes. On a mismatch (two pink arrows) it takes the larger of the up cell dp[i-1][j] (drop $X$ 's last letter) and the left cell dp[i][j-1] (drop $Y$ 's last letter).

Now apply the full 5-step recipe:

State. dp[i][j] = length of the LCS of the first $i$ letters of $X$ and first $j$ letters of $Y$ (as defined above).
Recurrence. The match/mismatch cases shown above. Why this step? If the last letters match they must be reusable as the tail of a common subsequence; if not, the answer ignores one of the two last letters, so we try both and keep the better.
Table dimensions & base. Allocate a grid dp of size $(∣ X ∣ + 1) \times (∣ Y ∣ + 1) = 8 \times 6$ — one extra row and column for the empty prefix. Initialise row 0 and column 0 to all zeros. Why this step? An empty string shares no letters with anything, so its LCS length is 0; and the recurrence at $i = 1$ or $j = 1$ must read a valid row 0 / column 0.
Order. Fill row by row (increasing $i$ ), and within each row left to right (increasing $j$ ). Why this step? Each cell reads up (dp[i-1][j]), left (dp[i][j-1]) and up-left (dp[i-1][j-1]); this order guarantees all three are already filled before we read them.
Answer. The bottom-right cell dp[|X|][|Y|] = dp[7][5]. Why this step? That cell is the LCS of the whole $X$ against the whole $Y$ .

Here is the full table (rows = letters of $X =$ ABCBDAB top-to-bottom, columns = letters of $Y =$ BDCAB left-to-right). Row/col 0 are the empty-prefix zeros.

	B	D	C	A	B
∅	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	2
C	1	1	2	2	2
B	1	1	2	2	3
D	1	2	2	2	3
A	1	2	2	3	3
B	1	2	2	3	4

Read a few cells to see the rules fire:

Row A, col A: letters match (A=A) → up-left 0 + 1 = 1.
Row B, col B (last column): match (B=B) → up-left cell (row A, col A = 1) + 1 = 2.
Row C, col C: match → up-left (row B, col D = 1) + 1 = 2.
Bottom-right (row B, col B): match → up-left (row A, col A = 3) + 1 = 4.
A mismatch example — row B, col D: B≠D → max(up = 0, left = 1) = 1.

The bottom-right cell is 4 — one witnessing subsequence is "BCAB".

Verify: "BCAB" appears in order in both ABCBDAB and BDCAB, and no length-5 common subsequence exists. LCS length = 4. ✅

Ex 7 — C7: a real-world word problem (max non-adjacent loot)

Forecast: grabbing the two biggest, 9 and 7, would clash (adjacent). What's the real max?

The English constraint "no two adjacent" becomes a take/skip decision per house — pure tabulation. Let $a_{i}$ mean "the cash in house $i$ " (0-indexed: $a_{0} = 2, a_{1} = 7, a_{2} = 9, a_{3} = 3, a_{4} = 1$ ).

State. dp[i] = max loot considering houses $0.. i$ . Why this step? Translate the informal goal into a box meaning.
Recurrence. For house $i$ with cash $a_{i}$ : either skip it (keep dp[i-1]) or rob it (take $a_{i}$ plus best from two houses back, dp[i-2], since $i - 1$ is now forbidden): $d p [i] = max (d p [i - 1], a_{i} + d p [i - 2]) .$ Why $d p [i - 2]$ ? Robbing house $i$ bans house $i - 1$ ; the nearest safe prior state is $i - 2$ .
Base. dp[0]=a_0=2; dp[1]=max(a_0,a_1)=max(2,7)=7. Why this step? With one or two houses there's no "two back" to recurse to.
Order. Increasing $i$ ; Answer. dp[4].

Filling in words:

dp[2] $= max (d p [1], a_{2} + d p [0]) = max (7, 9 + 2) = 11$ .
dp[3] $= max (d p [2], a_{3} + d p [1]) = max (11, 3 + 7) = 11$ .
dp[4] $= max (d p [3], a_{4} + d p [2]) = max (11, 1 + 11) = 12$ .

i	0	1	2	3	4
$a_{i}$	2	7	9	3	1
dp[i]	2	7	11	11	12

Verify: loot houses ${0, 2, 4} = 2 + 9 + 1 = 12$ . Any set avoiding adjacency: ${1, 3} = 10$ , ${0, 2} = 11$ , ${2, 4} = 10$ — none beat 12. Max = 12. ✅

Ex 8 — C8: the exam trap (a wrong "obvious" recurrence)

Forecast: the combinations of 4 from {1,2} are: 1+1+1+1, 1+1+2, 2+2 → 3 ways. Will the student's formula give 3?

The trap, worked out. The student's dp[a]=dp[a-1]+dp[a-2] is the Fibonacci/stairs shape — but that counts ordered sequences (it asks "was the last piece a 1 or a 2?", which distinguishes order). Let's actually run it with dp[0]=1, dp[1]=1:
- dp[2] $= d p [1] + d p [0] = 1 + 1 = 2$ .
- dp[3] $= d p [2] + d p [1] = 2 + 1 = 3$ .
- dp[4] $= d p [3] + d p [2] = 3 + 2 = 5$ .
So the student gets 5. Those 5 are the ordered writings 1111, 112, 121, 211, 22 — it counts 112, 121, 211 as three different things, overcounting the one combination "two 1's and a 2." Why this step? We must see the wrong number appear to trust the fix.
The fix — coin outer loop. To count combinations, iterate coins on the outside, amounts inside:
```
dp = [0]*(amount+1); dp[0] = 1
for c in coins:            # commit to one coin type at a time
    for a in range(c, amount+1):
        dp[a] += dp[a-c]
```
Why this step (the crucial justification)? Putting the coin loop outside means we finish all decisions about coin 1 before we ever touch coin 2. Once we move to coin 2, we can only append 2's on top of amounts already built from 1's — we never go back and interleave a 1 after a 2. That fixed processing order (all 1's, then all 2's) makes every multiset appear in exactly one canonical order, so reorderings like 112 vs 121 can never both be counted. Swap the loops (amount outside, coin inside) and you'd re-introduce every ordering → back to counting permutations.
Trace (coins ${1, 2}$ , amount 4). After the coin-1 pass, every amount has exactly one way (all 1's): dp = [1,1,1,1,1]. Now the coin-2 pass does dp[a] += dp[a-2] for $a = 2..4$ :
- dp[2] += dp[0]: $1 + 1 = 2$ .
- dp[3] += dp[1]: $1 + 1 = 2$ .
- dp[4] += dp[2]: $1 + 2 = 3$ .

a	0	1	2	3	4
after coin 1	1	1	1	1	1
after coin 2	1	1	2	2	3

Answer. dp[4] = 3 — matching our hand count {1111, 112, 22}.

Verify: combinations of 4 from {1,2} = {1111,112,22} = 3; the naive stairs recurrence overcounts to 5. ✅

Recall Scenario checklist before you code any tabulation

Did I handle the degenerate input (empty / zero)? (Ex 2)
Does any state mean "impossible" — and is my sentinel min/max-safe? (Ex 4)
Is my loop direction right for in-place / 1D collapse? (Ex 5)
Am I counting order or combinations — is the loop nesting correct? (Ex 8)

Active recall

Tribonacci base cases — how many do you need and why?

Three (dp[0],dp[1],dp[2]) because the recurrence reaches back 3 steps; fewer would read a negative index.

Why is dp[0]=1 (not 0) in climbing-stairs / counting DP?

The empty sequence of moves is one valid way; using 0 would break downstream sums.

In Coin Change min-coins, why initialise unreachable cells to ∞ not −1?

So the min() never wrongly picks an impossible path; −1 looks smaller and corrupts the min.

1D 0/1 knapsack: which capacity loop direction and why?

High→low, so dp[c−w] still holds the previous item's value (no reuse).

LCS match vs mismatch recurrence?

Match: dp[i−1][j−1]+1; mismatch: max(dp[i−1][j], dp[i][j−1]).

LCS table dimensions and base?

Size (|X|+1)×(|Y|+1); row 0 and column 0 all zeros (empty prefix shares nothing).

House robber recurrence?

dp[i]=max(dp[i−1], a_i+dp[i−2]); robbing i forbids i−1 so we fall back to i−2.

Coin Change: ordered count vs combination count — what changes?

Combination count puts the coin loop OUTSIDE the amount loop; ordered count puts amount outside.

Connections

Tabulation (bottom-up DP) — iterative (index 3.7.8) — the parent recipe these examples exercise
0-1 Knapsack, Coin Change, Longest Common Subsequence — the classic tables traced here
Space Optimization in DP — the 1D collapse of Ex 5
Recurrence Relations — where each recurrence comes from
Optimal Substructure, Overlapping Subproblems — why every example even works
Memoization (top-down DP) — the top-down twin