DP problems — Fibonacci, coin change (count + min), 0 - 1 knapsack: Worked examples

The scenario matrix

Before working examples, let's list every distinct situation these four DP problems can hand you. Each row is a "case class"; the last column names the example that nails it.

#	Case class	What's special / where beginners break	Covered by
A	Fibonacci, ordinary $n$	build up from base — the "sticky note" walk	Ex 1
B	Fibonacci, degenerate $n = 0, 1$	recursion must stop before the recurrence	Ex 1
C	Coin count, reachable target	`dp[a]+=dp[a-c]`, coins outside	Ex 2
D	Coin count, target $= 0$	the "empty set" answer = 1, not 0	Ex 2
E	Coin min, greedy would fail	DP must beat greedy	Ex 3
F	Coin min, impossible target	answer must be $- 1$ , not a wrong number	Ex 4
G	0/1 knapsack, ordinary	2D table, look back to row $i - 1$	Ex 5
H	0/1 knapsack, capacity 0 / item too heavy	degenerate, nothing fits	Ex 6
I	0/1 knapsack, 1D reverse-loop correctness	the direction trap made concrete	Ex 7
J	Word problem (real world)	translate a story into weights/values	Ex 8
K	Exam twist — count vs permutations	loop-order changes the meaning	Ex 9

We now walk one example per interesting cell. Read the Forecast first and actually guess — the learning happens in the gap between your guess and the truth.

Ex 1 — Fibonacci, ordinary + degenerate (cells A, B)

Worked example Compute

$F (7)$ , and separately $F (0)$ and $F (1)$ . Forecast: write down what you think $F (7)$ is before reading on. (Sequence: $0, 1, 1, 2, 3, 5, 8, 13, \dots$ )

Step 1 — Handle the degenerate base first. $F (0) = 0$ , $F (1) = 1$ . These are given, not computed. Why this step? The recurrence $F (n) = F (n - 1) + F (n - 2)$ needs two earlier values; for $n = 0$ or $n = 1$ there aren't two earlier values, so the formula is undefined there. The base cases are the floor the recursion stands on — cell B is exactly "don't apply the formula too early."

Step 2 — Roll the table upward (space-optimized, keep only last two). Look at the figure: each new bar is the sum of the two behind it.

$i$	0	1	2	3	4	5	6	7
$F$	0	1	1	2	3	5	8	13

Why this step? Each entry uses only the two directly below it — the recurrence is local, which is precisely why $Θ (n)$ time and $O (1)$ memory suffice.

Verify: $F (6) + F (5) = 8 + 5 = 13 = F (7)$ ✅. And $F (0) = 0, F (1) = 1$ match the definition. ✅

Ex 2 — Coin change count, reachable + zero target (cells C, D)

Worked example

coins=[2,3], count ways to make amount = 6; also confirm amount = 0. Forecast: guess how many combinations of 2s and 3s sum to 6. (Hint: is $2 + 2 + 2$ one of them? Is $3 + 3$ ?)

Step 1 — Set the base. dp[0] = 1. Why this step? There is exactly one way to make 0 — take no coins (the empty set). That is cell D. If you set it to 0, every count downstream collapses to 0, because every real combination bottoms out at "make 0 with what's left."

Step 2 — Loop coins on the OUTSIDE. Why this step? We want combinations, not ordered sequences. Fixing coin order (first consider all uses of coin 2, then coin 3) means $2 + 3$ and $3 + 2$ are counted as the same thing exactly once. (Cell K below shows what breaks if you don't.)

Coin $2$ : for $a = 2 \dots 6$ do dp[a]+=dp[a-2]. $[1, 0, \underline{1}, 0, \underline{1}, 0, \underline{1}] \Rightarrow ways with only 2s: a = 0, 2, 4, 6$ Coin $3$ : for $a = 3 \dots 6$ do dp[a]+=dp[a-3]. $d p [3] + = d p [0] = 1, d p [4] + = d p [1] = 0, d p [5] + = d p [2] = 1, d p [6] + = d p [3] = 1$ Final dp = [1,0,1,1,1,1,2].

Verify: dp[6]=2. Enumerate by hand: $2 + 2 + 2$ and $3 + 3$ — exactly 2. ✅ dp[0]=1 (empty set) ✅.

Ex 3 — Coin change min, greedy trap (cell E)

Worked example

coins=[1,3,4], minimum coins for amount = 6. Forecast: greedy says "take the biggest coin first." What does greedy give? What's the real minimum? Guess both.

Step 1 — What greedy does (and why it's tempting). Biggest coin $\leq 6$ is $4$ ; remainder $2$ , then $1 + 1$ . Total $4 + 1 + 1 = 3$ coins. Why show this? For "nice" systems (1,5,10,25) greedy is optimal, so people over-trust it — see Greedy Algorithms. Here it lies.

Step 2 — DP tries every possible last coin. dp[0]=0, rest $\infty$ . $dp [a] = min_{c \leq a} (dp [a - c] + 1)$ Why the +1? One extra coin (the last one, $c$ ) added to the optimal way of making the rest $a - c$ — optimal substructure. Table:

$a$	0	1	2	3	4	5	6
dp	0	1	2	1	1	2	2

$d p [6] = min (d p [5], d p [3], d p [2]) + 1 = min (2, 1, 2) + 1 = 2$ (via coin $3$ , giving $3 + 3$ ).

Verify: DP $= 2$ ( $3 + 3$ ) beats greedy $= 3$ ( $4 + 1 + 1$ ). ✅ DP wins whenever denominations are arbitrary.

Ex 4 — Coin change min, impossible target (cell F)

Worked example

coins=[2,4], minimum coins for amount = 3. Forecast: can you even make 3 from 2s and 4s? What should the function return?

Step 1 — Recognize unreachability. All coins are even, target is odd. No combination of evens is odd. Why this step? A degenerate/impossible input must return a sentinel ( $- 1$ ), not a garbage number.

Step 2 — Watch the $\infty$ propagate. dp=[0,∞,∞,∞]. $d p [1]$ : no coin $\leq 1$ → stays $\infty$ . $d p [2] = d p [0] + 1 = 1$ . $d p [3]$ : only coin $2 \leq 3$ , so $d p [3] = d p [1] + 1 = \infty + 1 = \infty$ . Why this step? $\infty$ means "unreachable"; adding 1 to unreachable is still unreachable — the algebra of $\infty$ enforces correctness for free.

Step 3 — Convert sentinel to answer. return -1 if dp[3]==INF else dp[3] → -1.

Verify: $d p [3]$ never dropped below $\infty$ ⇒ return $- 1$ . Parity argument confirms it's truly impossible. ✅

Ex 5 — 0/1 knapsack, ordinary 2D (cell G)

Worked example

w=[1,3,4,5], v=[1,4,5,7], capacity W=7. Forecast: which subset maxes value under weight 7? Guess the value.

Step 1 — Set up the 2D state. dp[i][w] = best value using the first $i$ items with capacity $w$ . Row 0 (no items) and column 0 (no capacity) are all zeros. Why 2D? The future only cares about how many items remain and how much capacity is left — those two numbers are the state.

Step 2 — Fill each cell with skip-vs-take. Follow the figure: the red arrow (skip) copies straight down; the violet arrow (take) jumps back $w_{i}$ columns and up one row, then adds $v_{i}$ .

\underbrace{v_i+\text{dp}[i-1][w-w_i]}_{\text{take }i,\ \text{if }w_i\le w}\big)$$ *Why look back to row $i-1$ when taking?* Item $i$ is used **at most once**; after taking it we must continue with *earlier* items only — hence the previous row. The final cell `dp[4][7] = 9`. **Verify:** items 2 & 3 have weight $3{+}4=7\le7$ and value $4{+}5=9$. Item 4 alone $=7$; item $1{+}4$ $=8$. So **9** is best. ✅

Ex 6 — 0/1 knapsack, degenerate (zero capacity / item too heavy) (cell H)

Ex 7 — 0/1 knapsack, the 1D reverse-loop, made concrete (cell I)

Worked example

w=[2], v=[3], capacity W=6. Run the 1D array both loop directions and see the difference. Forecast: with ONE item of weight 2, you can take it at most once (0/1). Max value should be $3$ . What does a forward loop wrongly give?

Step 1 — Correct: iterate weight DOWNWARD. dp=[0,0,0,0,0,0,0], item weight 2, value 3. For $w = 6, 5, 4, 3, 2$ : dp[w]=max(dp[w], 3+dp[w-2]). Because we go downward, dp[w-2] still holds the old (item-not-yet-used) value $0$ , so every dp[w] becomes $max (0, 3 + 0) = 3$ . Final dp[6]=3. Why downward? It guarantees dp[w-2] refers to the state before this item — matching "use item once."

Step 2 — Wrong: iterate weight FORWARD (to expose the bug). For $w = 2, 4, 6$ : $d p [2] = 3$ ; then $d p [4] = 3 + d p [2] = 6$ ; then $d p [6] = 3 + d p [4] = 9$ . That's using the item three times — that's unbounded knapsack, not 0/1.

Verify: downward → dp[6]=3 (item taken once) ✅. Forward → dp[6]=9 (item taken thrice) — demonstrably the wrong paradigm for 0/1. ✅

Ex 8 — Word problem: the hiker's backpack (cell J)

Worked example A hiker's pack holds

10 kg. Available gear: tent (4 kg, worth 30 pts), stove (3 kg, 20 pts), sleeping bag (5 kg, 40 pts), camera (2 kg, 15 pts). Each item is unique (take it or leave it). Maximize points. Forecast: guess which items she should carry.

Step 1 — Translate the story into DP. Why this step? "Unique item, take-or-leave, weight budget, maximize value" is literally 0/1 knapsack. w=[4,3,5,2], v=[30,20,40,15], W=10.

Step 2 — Reason about candidate subsets under weight 10.

tent + sleeping bag + camera $= 4 + 5 + 2 = 11 > 10$ ✗ (over budget)
tent + stove + camera $= 4 + 3 + 2 = 9 \leq 10$ , value $30 + 20 + 15 = 65$
sleeping bag + tent $= 5 + 4 = 9 \leq 10$ , value $40 + 30 = 70$
sleeping bag + stove + camera $= 5 + 3 + 2 = 10 \leq 10$ , value $40 + 20 + 15 = 75$

Why check weight first? The capacity guard is the constraint; value only matters among feasible subsets.

Step 3 — DP confirms the max. The 0/1 table returns dp[4][10] = 75.

Verify: best feasible subset = {sleeping bag, stove, camera}, weight $10$ , value 75 — no feasible subset beats it. ✅ (Units: kg ≤ 10 ✔, points summed ✔.)

Ex 9 — Exam twist: count vs permutations (loop order flips the meaning) (cell K)

Worked example

coins=[1,2], target=3. Compute (a) number of combinations and (b) number of ordered sequences (permutations). Same recurrence, different loop order. Forecast: which number is bigger, and why?

Step 1 — Combinations (coins OUTSIDE). dp[0]=1. Coin 1: dp=[1,1,1,1]. Coin 2: $d p [2] + = d p [0] = 2, d p [3] + = d p [1] = 2$ → dp=[1,1,2,2]. dp[3]=2: the sets ${1, 1, 1}$ and ${1, 2}$ . Why coins outside? It forbids revisiting a coin in a new order, so $1 + 2$ and $2 + 1$ collapse to one.

Step 2 — Permutations (amount OUTSIDE, coins inside). dp[0]=1. For $a = 1 \dots 3$ : dp[a]=sum(dp[a-c] for c in coins, c<=a). $d p [1] = d p [0] = 1; d p [2] = d p [1] + d p [0] = 2; d p [3] = d p [2] + d p [1] = 2 + 1 = 3$ . dp[3]=3: the ordered sequences $1 + 1 + 1, 1 + 2, 2 + 1$ . Why amount outside? Now every position in the sequence may pick any coin freely, so order counts.

Verify: combinations $= 2$ , permutations $= 3$ . Permutations $\geq$ combinations because ordering splits ${1, 2}$ into two arrangements. ✅ Exam takeaway: the recurrence is the same; the loop order alone decides combinations vs permutations — see Tabulation vs Memoization.

Recall Self-test (reveal after answering)

Why does coin-change min return $- 1$ for coins=[2,4], amount=3? ::: All coins are even; an odd target is unreachable, so dp[3] stays $\infty$ and is converted to $- 1$ . In 1D 0/1 knapsack, which loop direction is correct and why? ::: Downward — it keeps dp[w-w_i] pointing at the state before the current item, enforcing "use each item at most once." What is dp[0] for coin-change count and why? ::: $1$ — there is exactly one way to make amount 0: the empty set. Same recurrence, coins-outside vs amount-outside gives what two meanings? ::: Coins outside = combinations (order ignored); amount outside = permutations (order counted).