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

Pattern: coin-change count. Signal words: "how many distinct combinations", "order does not matter", "unlimited supply". Loop order: coins on the OUTSIDE, amount inner going up. Recurrence dp[a] += dp[a-c], base dp[0] = 1. Why coins outside? If amount were outside, you would count 2+3 and 3+2 as two different sequences → permutations, not combinations. Fixing coin order once kills the double count.

Pattern: 0/1 knapsack. Signal: "each item usable once". The separating detail: in the 1D space-optimized form you iterate weight downward (W → w_i). That keeps dp[w - w_i] pointing at the previous item's answer, so item $i$ cannot be reused. Iterating upward would allow reuse → that is unbounded knapsack.

Base dp[0]=0, dp[1]=1. Then each dp[i]=dp[i-1]+dp[i-2]:

• dp[2]=1+0=1
• dp[3]=1+1=2
• dp[4]=2+1=3
• dp[5]=3+2=5
• dp[6]=5+3=8
• dp[7]=8+5=13

Full table: $[0,1,1,2,3,5,8,13]$, so $F(7)=13$. Why each step? Every entry needs only the two directly below it — the recurrence is local, which is exactly why one linear sweep suffices.

Start dp=[1,0,0,0,0,0,0] (index 0..6). dp[0]=1 = the empty selection.

• coin 1 (dp[a]+=dp[a-1]): $[1,1,1,1,1,1,1]$ — exactly one way per amount using only 1s.
• coin 2 (dp[a]+=dp[a-2], $a=\mathrm{2..6}$): dp[2]+=dp[0]→2, dp[3]+=dp[1]→2, dp[4]+=dp[2]→3, dp[5]+=dp[3]→3, dp[6]+=dp[4]→4 → $[1,1,2,2,3,3,4]$.
• coin 5 (dp[a]+=dp[a-5], $a=\mathrm{5..6}$): dp[5]+=dp[0]→4, dp[6]+=dp[1]→5 → $[1,1,2,2,3,4,5]$.

Answer: 5 ways to make 6. Enumerated: 1+1+1+1+1+1, 2+1+1+1+1, 2+2+1+1, 2+2+2, 5+1. ✅

dp[0]=0, rest start $\infty$. For each $a$, dp[a]=min over c(dp[a-c]+1):

• dp[1]=dp[0]+1=1
• dp[2]=dp[1]+1=2
• dp[3]=min(dp[2]+1, dp[0]+1)=min(3,1)=1 (one 3)
• dp[4]=min(dp[3]+1, dp[1]+1, dp[0]+1)=min(2,2,1)=1 (one 4)
• dp[5]=min(dp[4]+1, dp[2]+1, dp[1]+1)=min(2,3,2)=2 (4+1)
• dp[6]=min(dp[5]+1, dp[3]+1, dp[2]+1)=min(3,2,3)=2 (3+3)

Answer: 2 coins ( 3+3 ). Note greedy would grab 4 first → 4+1+1 = 3 coins, worse.

With amount outer / coin inner, each dp[a] sums over every coin at every amount independently, so it counts ordered sequences (permutations), not combinations. Trace dp=[1,0,0,0], amount a=1..3, coins c∈{1,2}:

• a=1: dp[1]+=dp[0]→1
• a=2: dp[2]+=dp[1](c=1)→1, dp[2]+=dp[0](c=2)→2
• a=3: dp[3]+=dp[2](c=1)→2, dp[3]+=dp[1](c=2)→2+1=3

Returns 3: the ordered sequences 1+1+1, 1+2, 2+1. The correct combination count is only 2 (1+1+1, 1+2). So the swap over-counts — it solves a different problem.

One item, weight 3, value 5. dp starts $[0,0,0,0,0,0,0]$ (index 0..6). Downward ($w=6\to 3$): each dp[w]=max(dp[w], 5+dp[w-3]).

• dp[6]=max(0, 5+dp[3])=max(0,5+0)=5
• dp[5]=max(0,5+dp[2])=5
• dp[4]=max(0,5+dp[1])=5
• dp[3]=max(0,5+dp[0])=5

Every dp[w-3] we read is still 0 (the pre-item value) because we haven't updated the lower cells yet. Result: value never exceeds 5 — the item is used at most once. ✅ If we went upward, dp[3] would become 5 first, then dp[6]=5+dp[3]=10 — using the single item twice (that's unbounded behaviour). The direction is the entire 0/1-vs-unbounded switch.

Build 2D dp[i][w] with dp[i][w]=max(dp[i-1][w], v_i+dp[i-1][w-w_i]). The parent already establishes dp[4][7]=9. Backtrack from dp[n][W]:

• dp[4][7]=9. Is it equal to dp[3][7]? dp[3][7] (items 1,2,3, cap 7) = 4+5 = 9. Equal ⇒ item 4 (v=7,w=5) was skipped. Move to dp[3][7].
• dp[3][7]=9 vs dp[2][7]. Items 1,2 max at cap 7 = 1+4 = 5. Not equal ⇒ item 3 (v=5,w=4) was taken. Subtract: go to dp[2][7-4]=dp[2][3].
• dp[2][3]=4 vs dp[1][3]=1. Not equal ⇒ item 2 (v=4,w=3) taken. Go to dp[1][3-3]=dp[1][0].
• dp[1][0]=0. Nothing left.

Chosen items: {2, 3} (weights 3+4 = 7, values 4+5 = 9). Max value 9. ✅ Why backtracking works: if dp[i][w]==dp[i-1][w] the item added nothing new, so it was skipped; otherwise it must have been the extra value, so it was taken.

This is subset sum — a 0/1 knapsack where "value" is just "reachable or not". Boolean can[a]: can[0]=True; for each number x, iterate a downward from 9 to x: can[a] = can[a] or can[a-x].

• start can[0]=True, rest False.
• x=3: can[3]=True.
• x=34: no cell ≥34 ≤9, nothing changes.
• x=4: can[7]|=can[3]→True, can[4]=True.
• x=12: too big, skip.
• x=5: can[9]|=can[4]→True, can[8]|=can[3]→True, can[5]=True.
• x=2: can[9]|=can[7] (already True), etc.

Answer: Yes, can[9]=True. A witness subset: 4 + 5 = 9 (or 3 + 4 + 2 = 9). ✅

State: dp[a][k] = number of combinations summing to a using exactly k coins, coins processed in fixed order (so combinations, not permutations). We want ${\sum }_{k=0}^{3}dp[5][k]$. Recurrence: loop coins outer, then a, then k: $dp[a][k]+=dp[a-c][k-1]$ Base dp[0][0]=1. Reasoning: adding one coin c raises the sum by c and the count by 1.

Compute (coins order 1 then 2), collecting dp[5][k] for k=1,2,3: To make 5 with coins in $\{1,2\}$ and at most 3 coins:

• 5 coins of 1 → 5 coins (exceeds 3, excluded).
• 2+1+1+1 → 4 coins (excluded).
• 2+2+1 → 3 coins ✅.

Only 1 combination uses ≤3 coins. Answer: 1. Why the extra dimension? The constraint "at most 3 coins" is not a function of a alone, so it must live in the state — classic sign that you need an added dimension.

• 2D: time $\Theta (nW)$ (fill every cell once, $O(1)$ work each), space $\Theta (nW)$.
• 1D: time $\Theta (nW)$ (same), space $\Theta (W)$ (only one weight-row kept).

When 1D: you only need the optimal value → use 1D, it's asymptotically the same time and much lighter memory. When 2D: you must reconstruct the chosen items (Ex 4.1) → you need the full history, so keep the 2D table (or store parent pointers). See Time and Space Complexity. Note $\Theta (nW)$ is pseudo-polynomial — it depends on the numeric value $W$, not just its bit-length, so a huge $W$ is genuinely expensive.

Recognize the aggregation (count = +=, optimize = max/min); pick loop order to encode combinations-vs-reuse; set the base as the answer to the trivial question; add a state dimension only when a constraint can't be read off the current cell; and remember $\Theta (nW)$ is pseudo-polynomial.