Chapter 4 · Dynamic Programming

01 What is Dynamic Programming?

"Dynamic programming solves problems by combining the solutions to subproblems. In contrast [to divide and conquer], dynamic programming is applicable when the subproblems are not independent — when they share common sub-subproblems. In such cases, a divide-and-conquer algorithm does more work than necessary by repeatedly solving the same subsubproblem. A dynamic-programming algorithm solves each subsubproblem only once and stores its result in a table, avoiding recomputation whenever the same subsubproblem is encountered again."

Divide & Conquer

Overlapping subproblems → O(2ⁿ)

Recomputes the same subproblems exponentially many times (e.g., naïve Fibonacci, matrix chain).

→

Dynamic Programming

Memoize → polynomial

Compute each subproblem once. Store in a table. Fill bottom-up to avoid recursion overhead.

🔍

1 · Optimal Substructure

An optimal solution contains optimal solutions to subproblems. This is the key property that makes DP applicable.

🔗

2 · Overlapping Subproblems

The same subproblems recur many times. Store each result once to avoid exponential recomputation.

📋

3 · Bottom-Up Fill

Build the solution table from smallest subproblems upward. When we need m[i,j], all smaller subproblems are already solved.

"We will develop a dynamic programming algorithm in two stages: first as a recursive procedure, and then by reinterpreting this procedure, as an iterative algorithm that builds up solutions to progressively larger subproblems."

02 Matrix-Chain Multiplication

Given a sequence of n matrices A₁, A₂, …, Aₙ, compute their product A₁A₂⋯Aₙ. Matrix multiplication is associative, so any parenthesization gives the same result — but the cost (number of scalar multiplications) can vary dramatically.

Why parenthesization matters

Matrices: A₁ = 10×100, A₂ = 100×5, A₃ = 5×50. Computing (A₁A₂)A₃ costs 7,500 multiplications. Computing A₁(A₂A₃) costs 75,000 — 10× more. The goal is to find the parenthesization that minimizes total scalar multiplications.

Why Not Brute Force?

Let P(n) = number of possible parenthesizations. The recurrence P(n) = Σ P(k)·P(n−k) yields the Catalan numbers, which grow as Ω(4ⁿ / n^(3/2)) — exponential in n. We need a smarter approach.

Optimal Substructure

Proposition

Suppose the optimal parenthesization of AᵢAᵢ₊₁⋯Aⱼ splits the product between Aₖ and Aₖ₊₁. Then the parenthesizations of the subproducts Aᵢ⋯Aₖ and Aₖ₊₁⋯Aⱼ are also optimal.

Proof sketch

If there were a lower-cost parenthesization of, say, Aᵢ⋯Aₖ, then substituting it into the optimal parenthesization of Aᵢ⋯Aⱼ would yield a lower-cost parenthesization of Aᵢ⋯Aⱼ, a contradiction.

■

DP Recurrence

Let m[i,j] = minimum scalar multiplications needed to compute Aᵢ…Aⱼ, where Aₘ has dimensions p_{m−1} × pₘ. The input array is p = [p₀, p₁, …, pₙ].

\[m[i,j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k < j}\{m[i,k] + m[k+1,j] + p_{i-1} p_k p_j\} & \text{if } i < j \end{cases}\]

Algorithm — O(n³)

MatrixChainMultiplication(p)

for i=1 to n: m[i,i]=0 // base case: single matrix for l=2 to n: // l = chain length for i=1 to n-l+1: j = i+l-1 m[i,j] = ∞ for k=i to j-1: // try all split points q = m[i,k]+m[k+1,j]+p[i-1]·p[k]·p[j] if q < m[i,j]: m[i,j]=q; s[i,j]=k return m, s

The three nested loops each range over at most n values, giving O(n³) total time. Only the upper triangle of m[i,j] (where i ≤ j) is used.

🔢 Matrix Chain DP Table Interactive

4 matrices with dimensions p = [30, 35, 15, 5, 10]. Filling the m[i,j] table bottom-up (by chain length l). Press Next to advance.

Chain length l = —

Best split k = —

Optimal cost m[1,4] = ?

Filled

Currently computing

Empty (i > j)

To reconstruct the optimal parenthesization, a second table s[i,j] records the split index k achieving the minimum. Recursion on s gives the optimal order in O(n) time.

03 Sequence Alignment

How should a dictionary decide what you "probably meant" when you type ocurrance? It finds the most "similar" word using sequence alignment — a framework due to Needleman and Wunsch (early 1970s) that remains the standard in bioinformatics today.

Definition

Sequence Alignment

Given sequences X = (x₁,…,xₘ) and Y = (y₁,…,yₙ), a matching M between positions of X and Y is a sequence alignment if whenever (i,j),(i',j') ∈ M with i < i', we have j < j' (order-preserving).

The cost of M = gap penalties + mismatch costs:

Each unmatched position (gap) costs g > 0
Each matched pair (i,j) costs c[xᵢ, yⱼ] (0 if xᵢ = yⱼ)

Example Alignment

X = (G,A,T,C,G,G,C,A,T) and Y = (C,A,A,T,G,T,G,A,A,T,C):

G - A T C G - G C A T -
C A A T - G T G A A T C

Dashes are gaps. The goal is to find the alignment minimizing total gap + mismatch cost.

Optimal Substructure

Proposition — 3 Cases

Let M be an optimal alignment of X to Y. Then one of:

(1) (m,n) ∈ M — last characters are matched
(2) The mth position of X is not in M — gap in X
(3) The nth position of Y is not in M — gap in Y

Proof: If both (m,j)∈M and (i,n)∈M with i<m but j<n, then i<m and j<n — contradicting that the alignment is order-preserving.

Recurrence

Let a[i,j] = cost of optimal alignment of Xᵢ (prefix of X of length i) with Yⱼ.

\[a[i,j] = \min\bigl\{c[x_i, y_j] + a[i-1,j-1],\; g + a[i-1,j],\; g + a[i,j-1]\bigr\}\]

Base cases: a[i,0] = ig (gap out all of Xᵢ) and a[0,j] = jg.

Algorithm — O(mn)

SequenceAlignment(X, Y)

for j=0 to n: a[0,j] = j·g // base: all gaps for i=1 to m: a[i,0] = i·g for j=1 to n: a[i,j] = c[xᵢ,yⱼ] + a[i-1,j-1] // match/mismatch if g+a[i-1,j] < a[i,j]: a[i,j] = g+a[i-1,j] // gap in Y if g+a[i,j-1] < a[i,j]: a[i,j] = g+a[i,j-1] // gap in X b[i,j] = pointer to the choice above return a, b

The table a[0:m, 0:n] is filled in row-major order in O(mn) time. Backtracking through b[i,j] from b[m,n] recovers the optimal alignment in O(m+n) time.

Backtracking rule

Moving from b[i,j] to b[i−1,j−1] means pair (i,j) is in the alignment. Moving to b[i−1,j] means gap in Y at position j. Moving to b[i,j−1] means gap in X at position i.

04 Longest Common Subsequence

A subsequence of X = (x₁,…,xₘ) is obtained by deleting some elements without changing order. The longest common subsequence (LCS) of X and Y is the longest sequence that is a subsequence of both.

Example

X = (A,B,C,B,D,A,B), Y = (B,D,C,A,B,A) → LCS = (B,C,B,A), length 4. Since X has 2⁷ = 128 subsequences, checking all is inefficient. DP gives O(mn).

Optimal Substructure — 3 Cases

Let Z = (z₁,…,zₖ) be an LCS of X and Y.

(1) If xₘ = yₙ, then zₖ = xₘ = yₙ, and Z_{k−1} is an LCS of X_{m−1} and Y_{n−1}
(2) If xₘ ≠ yₙ and zₖ ≠ xₘ, then Z is an LCS of X_{m−1} and Y
(3) If xₘ ≠ yₙ and zₖ ≠ yₙ, then Z is an LCS of X and Y_{n−1}

Recurrence

Let a[i,j] = length of LCS of Xᵢ and Yⱼ.

\[a[i,j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ a[i-1,j-1]+1 & \text{if } x_i = y_j \\ \max\{a[i-1,j],\, a[i,j-1]\} & \text{if } x_i \ne y_j \end{cases}\]

📏 LCS Table Visualizer Interactive

X = (A,B,C,B,D,A,B), Y = (B,D,C,A,B,A). Press Next to fill the DP table cell by cell.

Computing a[—, —]

LCS length = ?

Match (xᵢ=yⱼ, +1)

Filled

LCS path

Current

Recovery — O(m + n)

PrintLCS(b, X, i, j)

if i=0 or j=0: return if b[i,j]=(i-1,j-1): PrintLCS(b,X,i-1,j-1) print xᵢ // matched element else if b[i,j]=(i-1,j): PrintLCS(b,X,i-1,j) // gap in Y else: PrintLCS(b,X,i,j-1) // gap in X

05 The Knapsack Problem

A hiker carries a knapsack of capacity W. There are n items, each with weight wᵢ and value vᵢ. Select a subset to maximize total value without exceeding W.

Exponential brute force

Checking all 2ⁿ subsets is impractical. DP gives O(nW) — but beware: this is pseudopolynomial. W needs only O(log W) bits to represent, so O(nW) is actually exponential in the input length. The knapsack problem is NP-hard.

Subproblems & Recurrence

Let a[i,j] = max value using items t₁,…,tᵢ with weight budget j.

\[a[i,j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ a[i-1,j] & \text{if } w_i > j \\ \max\{v_i + a[i-1,j-w_i],\; a[i-1,j]\} & \text{if } w_i \le j \end{cases}\]

Algorithm — O(nW)

Knapsack(n, v, w, W)

for j=0 to W: a[0,j]=0 for i=1 to n: a[i,0]=0; b[i,0]=FALSE for j=1 to W: if wᵢ>j: a[i,j]=a[i-1,j]; b[i,j]=FALSE // item too heavy else if vᵢ+a[i-1,j-wᵢ] > a[i-1,j]: a[i,j]=vᵢ+a[i-1,j-wᵢ]; b[i,j]=TRUE // take item else: a[i,j]=a[i-1,j]; b[i,j]=FALSE // skip item return a, b

🎒 Knapsack Solver Interactive

4 items with W=7 capacity. Press Next to fill a[i,j] row by row.

Row i = —

Column j = —

Optimal value = ?

Recovery — O(n)

Backtrack through b[n,W]: if b[i,j] = TRUE, include item i, then move to b[i−1, j−wᵢ]. Otherwise skip item i and move to b[i−1, j].

06 Change-Making Problem

Given coin denominations d₁, d₂, …, dₖ (with d₁ = 1) and a target N, find the minimum number of coins to make change for N.

Greedy fails in general

For coins {1,5,10,25}: N=17 → greedy: 10+5+1+1 = 4 coins ✓ But for coins {1,5,9,16}: N=18 → greedy: 16+1+1 = 3 coins ✗ Optimal: 9+9 = 2 coins. Greedy is suboptimal!

Greedy is Optimal for {1, 5, 10, 25}

The notes prove this by an exchange argument with four cases:

Case 1 — 1 ≤ N < 5

d = 1. Any solution must use coins of denomination 1, so greedy is trivially optimal.

Case 2 — 5 ≤ N < 10

d = 5. If optimal skips d=5, it uses only 1s. Replacing five 1s with one 5 gives fewer coins — contradiction.

Case 3 — 10 ≤ N < 25

d = 10. If optimal skips d=10, coins of 1 and 5 must sum to 10; replace with one 10 — contradiction.

Case 4 — N ≥ 25

d = 25. ≥3 coins of 10 → swap for 25+5 (fewer coins). At most 2 tens → some 1s/5s/10s sum to 25 → swap for one 25.

DP Algorithm — always correct

Let a[i] = minimum coins to make change for value i.

\[a[i] = 1 + \min\{a[i - d_j] \mid 1 \le j \le k, d_j \le i\}\]

Algorithm — O(Nk)

ChangeMaking(N, d)

a[0]=0 for i=1 to N: a[i] = ∞ for j=1 to k: if i≥dⱼ AND 1+a[i-dⱼ] < a[i]: a[i] = 1+a[i-dⱼ] b[i] = dⱼ // which coin was used return a, b Pay(i,b): if i>0: print b[i]; Pay(i-b[i], b)

Also pseudopolynomial

O(Nk) is exponential in the bit-length of N. For arbitrary coin denominations, the change-making problem is NP-hard. But for fixed small denominations like {1,5,10,25}, it runs in O(N) constant-bounded loop iterations.

💰 Change-Making Simulator Interactive

N =

Enter an amount N (1–99) and click Solve to find the minimum coins using DP, then compare with greedy.

Available denominations:

1¢

5¢

10¢

25¢

Chapter Summary

Problem	Key Recurrence	Table Size	Time	NP-hard?
Matrix-Chain Mult.	m[i,j] = min over splits k	n × n	O(n³)	No
Sequence Alignment	a[i,j] = min{match, gap×2}	m × n	O(mn)	No
Longest Common Subseq.	a[i,j] = a[i-1,j-1]+1 or max	m × n	O(mn)	No
Knapsack	a[i,j] = max{take, skip}	n × W	O(nW) *	Yes
Change-Making	a[i] = 1 + min over coins	N	O(Nk) *	Yes (general)

* Pseudopolynomial — polynomial in the value W or N, not in the bit-length of the input.

The DP pattern

Every DP in this chapter follows the same playbook: (1) identify a 2–3 case optimal substructure, (2) write a recurrence for the optimal value of each subproblem, (3) fill the table bottom-up so dependencies are already computed, (4) backtrack through a pointer table to recover the actual solution. The art is in choosing the right subproblem definition.

DP vs. Greedy

The change-making section shows a clean separation: greedy is correct (and O(1)!) for denominations {1,5,10,25} — proven by case analysis. But DP is always correct for any coin set. When a greedy exchange argument goes through, prefer greedy. When it doesn't, reach for DP.