Dynamic programming — overlapping subproblems, optimal substructure: Worked examples

This page is the exhaustive drill room for Dynamic Programming. The parent note gave you the idea. Here we walk through every kind of case a DP problem can throw at you — so that when an exam or an interview hands you a weird corner, you have already seen its twin.

Before line one: DP means "recursion + remembering answers"; a subproblem is a smaller version of the original question (like $F (3)$ inside $F (5)$ ); a recurrence is the formula that builds a bigger answer from smaller ones; a base case is the smallest subproblem whose answer we just know without recursing. Every symbol below is built on these four words.

The scenario matrix

Every DP problem falls into one of these case classes. The examples below are labelled by which cell they hit. If you can solve every cell, no DP problem can surprise you.

#	Case class	What makes it tricky	Example that covers it
C1	1-D DP, tiny base	pick the right base case	Ex 1 — Fibonacci at the edge
C2	Degenerate / zero input	$n = 0$ , empty array, capacity 0	Ex 2 — Knapsack with $W = 0$
C3	2-D DP grid	two indices move together	Ex 3 — Longest Common Subsequence
C4	"Take vs skip" choice	a decision at each item	Ex 4 — Knapsack full trace
C5	Overlap present, substructure ABSENT	DP gives the wrong answer	Ex 5 — Longest simple path trap
C6	Overlap ABSENT	DP wastes memory, no speedup	Ex 6 — Merge Sort
C7	Real-world word problem	translate prose → recurrence	Ex 7 — Coin change (fewest coins)
C8	Negative values / limiting behaviour	signs and $\infty$ sentinels	Ex 8 — Bellman-Ford relaxation
C9	Exam twist: wrong fill order	spot the bug	Ex 9 — Broken tabulation

Ex 1 — C1: 1-D DP, the tiny base case

Forecast: Guess the value of $F (6)$ and how many additions bottom-up needs before reading on.

Figure — Dynamic programming — overlapping subproblems, optimal substructure

Write the base cells. $d p [0] = 0$ , $d p [1] = 1$ . Why this step? The recurrence $F (n) = F (n - 1) + F (n - 2)$ reaches down two steps, so we must know the two smallest before any loop starts. Without both bases, $d p [2]$ has nothing to read.
Fill upward $i = 2 \dots 6$ (look at the green arrows in the figure, each cell pulls from the two cells to its left): $d p [2] = 1, d p [3] = 2, d p [4] = 3, d p [5] = 5, d p [6] = 8$ . Why this step? Filling in increasing $i$ guarantees $d p [i - 1]$ and $d p [i - 2]$ are already computed — this is optimal substructure turned into a loop order.
Count additions. One addition per new cell, cells $2$ through $6$ = 5 additions. Why this step? Complexity $= (# subproblems) \times (work each)$ ; here $\approx n$ subproblems $\times O (1)$ .

Verify: $F (6) = 8$ matches the classic sequence $0, 1, 1, 2, 3, 5, 8$ . Naive recursion would make $F (6)$ spawn $\approx 25$ calls — our 5 additions confirm the $O (2^{n}) \to O (n)$ collapse.

Ex 2 — C2: the degenerate zero input

Forecast: Will the algorithm crash, or return something sensible?

Capacity 0 case. The recurrence's "take" branch needs $w_{i} \leq c$ . With $c = 0$ and every $w_{i} \geq 1$ , that branch is never allowed, so $K (i, 0) = K (i - 1, 0) = \dots = 0$ . Why this step? We must show the recurrence's guard clause $w_{i} > c$ handles the boundary — no item fits, so value stays 0.
Zero items case. The base row $K (0, c) = 0$ for all $c$ . Why this step? With nothing to pack, the optimum is trivially 0 regardless of capacity. Degenerate inputs live entirely in the base case.

Verify: Both answers are $0$ . Sanity: value can't be negative and no item was ever placed, so 0 is the only possible packed value. Units: value stays in "value points," capacity in "weight units" — no unit mixing occurred.

Ex 3 — C3: the 2-D DP grid (LCS)

Forecast: Guess the length. (A subsequence keeps order but may drop letters.)

Let $L (i, j)$ = LCS length of the first $i$ letters of string $X$ and first $j$ letters of string $Y$ .

Base cells. $L (0, j) = L (i, 0) = 0$ : an empty prefix shares nothing. Why this step? Two indices $\Rightarrow$ a 2-D table; the base is the whole first row and column (empty-string cases).
Recurrence. If the letters match, extend the diagonal: $L (i, j) = {L (i - 1, j - 1) + 1 max (L (i - 1, j), L (i, j - 1)) X_{i} = Y_{j} X_{i} \neq = Y_{j}$ Why this step? A match means both strings gained the same letter — the optimal answer must include it (optimal substructure), so we jump diagonally and add 1. A mismatch means we drop one letter from one string and take the better of the two.
Fill the grid row by row (the blue diagonal arrows in the figure are the "+1 on match" moves). The bottom-right cell is the answer: 4 ("BCAB"). Why this step? Each $(i, j)$ reads only cells above/left/diagonal — all filled earlier — so left-to-right, top-to-bottom respects every dependency.

Verify: "BCAB" is length 4, appears in order in both A**B**C**B**D**A****B** and **B**D**C****A****B**. No length-5 common subsequence exists. Answer $= 4$ . ✓

Ex 4 — C4: full "take vs skip" trace

Forecast: Greedy-by-ratio would grab item 1 (ratio 1), then item 2 (ratio 1.33)… guess whether greedy even gets the right answer here.

Recurrence (from the parent): $K (i, c) = max (K (i - 1, c), v_{i} + K (i - 1, c - w_{i}))$ when $w_{i} \leq c$ . Why this step? At each item we either skip (value $K (i - 1, c)$ ) or take it (gain $v_{i}$ , shrink capacity). Optimal substructure guarantees the best of two optimal sub-answers is optimal overall.
Consider taking items 2 and 4 ( $w = 3 + 5 = 8 > 7$ ) — too heavy, blocked. Why this step? The guard $w_{i} \leq c$ prunes infeasible combos; we must respect capacity at every branch.
Best feasible combo: items 2 and 3 ( $w = 3 + 4 = 7 = W$ , $v = 4 + 5 = 9$ ). Why this step? We compare against item 1+3 ( $w = 5$ , $v = 6$ ), item 4 alone ( $v = 7$ ), item 2+3 ( $v = 9$ ) — the DP table quietly checks all of these and keeps the max.

Verify: $K (4, 7) = 9$ . Check the greedy trap: greedy by ratio ( $1, 1.33, 1.25, 1.4$ ) grabs item 4 first (ratio 1.4, value 7, weight 5), then only item 1 fits (weight 6, value 8) — greedy scores 8 < 9. This is exactly the "greedy fails 0/1" mistake. DP wins. ✓

Ex 5 — C5: overlap present but NO optimal substructure

Forecast: DP runs and returns a number — will it be correct?

Try the naive substructure claim: "longest simple path to D = longest simple path to C, then C→D." Why this step? We test whether the whole optimum is built from sub-optima — the definition of optimal substructure.
Find the counterexample. Longest simple path to C might be A→B→C (uses B). But the longest simple path to D via C might need to avoid B for a different route — the sub-answer "best path to C" forgets which vertices it already used. Why this step? Simple paths forbid revisiting, so a cached sub-answer is only valid for one specific set of used vertices — the cache key (node) is incomplete.
Conclusion: memoizing on node alone gives a wrong answer, even though subproblems overlap. Why this step? Overlap makes caching tempting; the missing optimal substructure makes it incorrect. You must prove substructure first.

Verify: The true longest simple A→D path here is A→B→C→D (length 3 edges). A naive memo keyed only on the node cannot distinguish it from the shorter A→C→D (length 2), so it may return the wrong path — demonstrating the failure. (Longest-simple-path is NP-hard precisely for this reason.) ✓

Ex 6 — C6: overlap ABSENT — DP is pointless

Forecast: Would a cache ever get a hit?

List the subproblems: sort [5,2,8,1] → sort [5,2] and [8,1] → sort [5],[2],[8],[1]. Why this step? We enumerate to check for repeats — the only thing a cache exploits.
Check for overlap: every sub-array is a distinct slice. No two recursive calls ask the same question. Why this step? No repeats ⇒ no cache hit ⇒ zero time saved, only memory wasted.

Verify: Merge Sort is $O (n lo g n)$ with no DP; a cache of size $O (n)$ would deliver 0 hits on all-distinct inputs. Confirms the parent's "not every recursion should be DP'd." See Recursion Trees to visualise the disjoint tree. ✓

Ex 7 — C7: real-world word problem (coin change)

Forecast: Greedy grabs the biggest coin first (4, then 1, then 1 = 3 coins). Is greedy optimal?

Define the subproblem. $M (a)$ = fewest coins to make amount $a$ . Base: $M (0) = 0$ . Why this step? Translating prose to a recurrence: "make $a$ " shrinks to "make $a - coin$ " after using one coin.
Recurrence. $M (a) = 1 + min_{coin c \leq a} M (a - c)$ . Why this step? Using one coin $c$ leaves amount $a - c$ ; the best overall is 1 (this coin) plus the best way to make the rest — optimal substructure holds because sub-amounts don't "interfere."
Fill up $a = 1 \dots 6$ : $M (1) = 1, M (2) = 2, M (3) = 1, M (4) = 1, M (5) = 2, M (6) = 2$ (coins $3 + 3$ ). Why this step? Bottom-up so each $M (a - c)$ is ready before we read it.

Verify: $M (6) = 2$ (using $3 + 3$ ). Greedy scored 3 ( $4 + 1 + 1$ ) — greedy is wrong here, DP is right. Sanity: $3 + 3 = 6$ ✓, and no single coin equals 6, so 2 is minimal. ✓

Ex 8 — C8: negative weights & limiting sentinels (Bellman-Ford)

Forecast: Does the direct edge (5) or the detour through A win, given the negative edge?

Initialise. $d i s t [S] = 0$ , everything else $= + \infty$ . Why this step? $+ \infty$ is the sentinel meaning "unreached." Relaxation only improves finite-or-infinite estimates downward.
Relax each edge (the DP update $d i s t [y] = min (d i s t [y], d i s t [x] + w)$ ): S→A: $d i s t [A] = 0 + 4 = 4$ . A→T: $d i s t [T] = 4 + (- 2) = 2$ . S→T: $min (2, 0 + 5) = 2$ . Why this step? Each relaxation is a "take this edge vs keep current best" choice — the same take/skip pattern as knapsack, but minimising and allowing negative edge weights.
Limiting note. If a negative cycle existed, distances would keep dropping past any bound — Bellman-Ford detects this by relaxing $∣ V ∣ - 1$ times then checking one more pass. Why this step? Covering the degenerate "no finite optimum" case.

Verify: $d i s t [T] = 2$ via S→A→T ( $4 - 2 = 2$ ), beating the direct 5. Handling of the negative edge is correct. ✓

Ex 9 — C9: the exam twist — spot the broken fill order

Worked example Statement

This tabulation is supposed to compute Fibonacci but returns garbage. Find the bug.

def fib(n):
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(n, 1, -1):        # ← suspicious
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Forecast: Which line violates the dependency direction?

Read the recurrence's dependency: $d p [i]$ needs $d p [i - 1]$ and $d p [i - 2]$ — smaller indices. Why this step? Tabulation's iron rule: fill an index only after everything it reads is filled.
Inspect the loop: range(n, 1, -1) counts downward from $n$ . So $d p [n]$ is computed first, reading $d p [n - 1]$ and $d p [n - 2]$ — both still 0. Why this step? Reading un-filled cells (all zero) is exactly the "wrong fill order" mistake from the parent note.
Fix: iterate upward: for i in range(2, n+1). Why this step? Increasing order guarantees dependencies are ready — matches Ex 1.

Verify: With the buggy downward loop and $n = 6$ , every read hits zeros, so $d p [6] = 0 + 0 = 0$ — wrong. The fixed upward loop yields $d p [6] = 8$ (Ex 1). ✓

Recall Which cell was hardest?

Which case makes DP return a wrong (not just slow) answer? ::: C5 — overlap present but no optimal substructure (longest simple path). Which case makes DP a waste of memory with no speedup? ::: C6 — no overlapping subproblems (Merge Sort). In coin change, why does greedy fail for coins {1,3,4} making 6? ::: Greedy takes 4+1+1=3 coins, but 3+3=2 coins is optimal; greedy-choice property doesn't hold.

Connections

Parent: DP topic note
Recursion · Recursion Trees — the trees these examples collapse.
Memoization vs Tabulation — top-down vs bottom-up, seen in Ex 1 & 9.
Knapsack Problem · Longest Common Subsequence · Bellman-Ford — the three canonical DPs drilled above.
Divide and Conquer — Ex 6's disjoint contrast. · Greedy Algorithms — Ex 4 & 7's failed shortcut.
Time Complexity Analysis — the $O (n)$ , $O (nW)$ counts.