Solve every subproblem once, write the answer down, and an exponential search collapses into a polynomial one.
Dynamic programming applies when a problem has overlapping subproblems — the naive recursion solves the same subproblem over and over. Divide-and-conquer generates disjoint subproblems and gains nothing from a table; dynamic programming generates shared ones and gains everything. It is typically used for optimisation problems, where many solutions exist and you want one with the best value. The chapter teaches it through four worked problems and then names the two properties a problem must have for the technique to apply.
Given a rod of length n and a table of prices pᵢ for rods of length i, cut the rod into pieces to maximise total revenue. Cuts are free and lengths are integers.
length i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
price pᵢ | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 |
A rod of length 4 can be cut 2³ = 8 ways, and in general there are 2n-1 ways — each of the n-1 internal positions is either cut or not. Brute force is exponential.
The recursive structure: make the first cut at some length i, take pᵢ, and solve the remaining rod of length n - i optimally.
rₙ = max over 1 ≤ i ≤ n of ( pᵢ + rn-i ) with r₀ = 0CUT-ROD(p, n) // naive: Θ(2ⁿ)
1 if n == 0
2 return 0
3 q = -∞
4 for i = 1 to n
5 q = max(q, p[i] + CUT-ROD(p, n-i))
6 return qCorrect, and hopeless. T(n) = 1 + ∑T(j) = 2ⁿ. The reason is visible in the recursion tree: CUT-ROD(p, 2) gets called many times and recomputes the same answer each time.
2ⁿ nodes but there are only n+1 distinct subproblems, r₀ through rₙ. Solve each once and store it, and the work collapses from exponential to Θ(n²). That is the whole idea of dynamic programming.| Top-down with memoisation | Bottom-up | |
|---|---|---|
| Shape | Ordinary recursion, plus a table checked on entry and filled on exit | Iterative, filling the table in order of increasing subproblem size |
| Solves | Only subproblems actually reachable | Every subproblem |
| Overhead | Recursive call frames | None |
| Prefer when | Some subproblems are never needed | All are needed — usually faster by a constant |
MEMOIZED-CUT-ROD-AUX(p, n, r)
1 if r[n] ≥ 0
2 return r[n] // already solved
3 if n == 0
4 q = 0
5 else q = -∞
6 for i = 1 to n
7 q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
8 r[n] = q // remember it
9 return q
BOTTOM-UP-CUT-ROD(p, n)
1 let r[0:n] be a new array
2 r[0] = 0
3 for j = 1 to n // subproblems in increasing size
4 q = -∞
5 for i = 1 to j
6 q = max(q, p[i] + r[j-i]) // r[j-i] is already known
7 r[j] = q
8 return r[n]Both are Θ(n²): a doubly nested loop over subproblem and choice. The bottom-up version is three lines and has no recursion at all.
n subproblems × n choices = Θ(n²).The table holds the optimal value. To recover the optimal cuts, store the choice that achieved each maximum in a second table.
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
1 let r[0:n] and s[1:n] be new arrays
2 r[0] = 0
3 for j = 1 to n
4 q = -∞
5 for i = 1 to j
6 if q < p[i] + r[j-i]
7 q = p[i] + r[j-i]
8 s[j] = i // remember the winning first cut
9 r[j] = q
10 return r and s
PRINT-CUT-ROD-SOLUTION(p, n)
1 (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
2 while n > 0
3 print s[n]
4 n = n - s[n]This pattern — a value table plus a choice table, then walk the choice table backwards — recurs in every DP in the chapter.
Matrix multiplication is associative, so A₁A₂A₃A₄ can be parenthesised many ways, all giving the same product but at wildly different costs. Multiplying a p×q matrix by a q×r matrix costs pqr scalar multiplications.
10×100, 100×5, 5×50: parenthesising as ((A₁A₂)A₃) costs 10·100·5 + 10·5·50 = 7,500. As (A₁(A₂A₃)) it costs 100·5·50 + 10·100·50 = 75,000. Ten times more, for the same answer.The number of parenthesisations of n matrices is the Catalan number, which is Ω(4ⁿ/n3/2) — exponential, so exhaustive search is out.
Subproblem: let m[i,j] be the minimum cost of computing Aᵢ⋯Aⱼ. The optimal parenthesisation splits at some k, and both halves must themselves be optimal.
╱ 0 if i == j
m[i,j] = │
╱ min over i ≤ k < j of ( m[i,k] + m[k+1,j] + pᵢ₋₁pₖpⱼ ) if i < jMATRIX-CHAIN-ORDER(p, n)
1 let m[1:n, 1:n] and s[1:n-1, 2:n] be new tables
2 for i = 1 to n
3 m[i, i] = 0
4 for l = 2 to n // l is the chain length
5 for i = 1 to n - l + 1
6 j = i + l - 1
7 m[i, j] = ∞
8 for k = i to j - 1
9 q = m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]
10 if q < m[i,j]
11 m[i,j] = q
12 s[i,j] = k // where to split
13 return m and sΘ(n³) time, Θ(n²) space. The outer loop over chain length is what guarantees the subproblems it reads are already solved.
m[i,j] depends on shorter chains, so you must fill by increasing length, not by row or column. Getting this order wrong is the most common bug when writing a table-based DP, and it is exactly what top-down memoisation frees you from having to think about.Section 14.3 names the two properties a problem must have.
u to v with the longest from v to w may reuse a vertex, so the result is not a simple path at all. The subproblems are not independent, the cut-and-paste argument fails, and no DP formulation works. This is exactly the pair from the NP-completeness table in Chapter 1.The chapter also distinguishes memoisation (top-down, lazy) from bottom-up (eager), and notes that when the subproblem graph is dense they cost the same, but memoisation wins when much of the space is never visited.
A subsequence is obtained by deleting zero or more elements without reordering. Given X = ⟨x₁,…,xₘ⟩ and Y = ⟨y₁,…,yₙ⟩, find a longest sequence that is a subsequence of both.
This is the algorithm behind diff, version-control merges, and DNA sequence comparison.
Theorem 14.1 (optimal substructure). Let Z be an LCS of X and Y. Then:
xᵐ = yₙ, then zₖ = xᵐ = yₙ and Zₖ₋₁ is an LCS of Xᵐ₋₁ and Yₙ₋₁.xᵐ ≠ yₙ, then Z is an LCS of Xᵐ₋₁ and Y, or of X and Yₙ₋₁. ╱ 0 if i == 0 or j == 0
c[i,j] = │ c[i-1, j-1] + 1 if i,j > 0 and xᵢ == yⱼ
╱ max( c[i-1, j], c[i, j-1] ) if i,j > 0 and xᵢ ≠ yⱼABCB and BDCB. Fill row by row; each cell reads only its left, upper, and diagonal neighbours.Cost: Θ(mn) time and space. Reconstruction walks backward from c[m,n] following the recorded direction, in O(m+n). If you only need the length, two rows suffice, giving Θ(min(m,n)) space — a standard optimisation the chapter mentions.
Given n keys in sorted order with search probabilities pᵢ, and n+1 dummy keys with probabilities qᵢ for unsuccessful searches, build the BST minimising expected search cost.
e[i,j] = min over i ≤ r ≤ j of ( e[i, r-1] + e[r+1, j] + w(i,j) )
where w(i,j) = ∑pₗ + ∑qₗ is the total probability weight of the subtreeThe w(i,j) term appears because making a subtree a child of a new root increases the depth of every node in it by one, adding its whole weight to the cost. Time is Θ(n³), space Θ(n²) — the same shape as matrix-chain, and for the same reason: a range subproblem with a choice of split point.
CLRS states the four steps once and uses them four times.
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute that value, typically bottom-up.
4. Construct an optimal solution from the computed information.Step 4 is optional if you only need the value. Steps 1 and 2 are where the thinking happens; step 3 is mechanical once the recurrence is right.
| Problem | Subproblems | Choices each | Time | Space |
|---|---|---|---|---|
| Rod cutting | n | n | Θ(n²) | Θ(n) |
| Matrix-chain | Θ(n²) | n | Θ(n³) | Θ(n²) |
| LCS | Θ(mn) | Θ(1) | Θ(mn) | Θ(mn) |
| Optimal BST | Θ(n²) | n | Θ(n³) | Θ(n²) |
Θ(n²), matrix-chain and optimal BST are Θ(n³) (range subproblems with a split choice), and LCS is Θ(mn).Chapter 15 covers greedy algorithms, which also need optimal substructure but replace the search over all choices with a single locally best one, committed to immediately and never reconsidered. When that works it is far faster than DP; the chapter is largely about how to tell whether it works.