What Makes Dynamic Programming Different from Divide-and-Conquer
Divide-and-conquer, discussed earlier in this series, breaks a problem into independent subproblems that share no work between them. Dynamic Programming applies to a different class of problems: ones where the subproblems overlap, meaning the same smaller subproblem is needed repeatedly across different branches of the recursion. Naive recursion would recompute these shared subproblems from scratch every time, wasting enormous amounts of work. Dynamic programming solves each distinct subproblem exactly once and stores the result for reuse.
The Rod-Cutting Problem: A First Complete Example
Given a rod of length n and a table of prices p[i] for rods of length i, the goal is to determine the maximum revenue obtainable by cutting the rod into pieces and selling those pieces.
Example price table:
Length i: 1 2 3 4 5 6 7 8
Price p: 1 5 8 9 10 17 17 20A rod of length 4 could be sold whole for 9, cut into two pieces of length 2 for 5+5=10, or cut into a piece of length 1 and length 3 for 1+8=9, and so on. The optimal solution for length 4 turns out to be cutting into two pieces of length 2, earning 10.
The Naive Recursive Solution
The revenue for a rod of length n can be expressed recursively: try every possible first cut of length i, and recursively solve for the best way to cut the remaining n-i.
CUT-ROD(p, n):
if n == 0:
return 0
q = -infinity
for i = 1 to n:
q = max(q, p[i] + CUT-ROD(p, n - i))
return qThis recursive formula is correct, but its running time is exponential: T(n) = Θ(2ⁿ), since it repeatedly recomputes the same subproblems. For example, computing CUT-ROD(p, 4) requires computing CUT-ROD(p, 2) multiple times through different recursive paths, and each of those recomputes CUT-ROD(p, 1) and CUT-ROD(p, 0) repeatedly.
Top-Down with Memoization
The first dynamic programming approach, Memoization, keeps the natural recursive structure but adds a table to store each subproblem's solution the first time it is computed, returning the cached value on subsequent requests instead of recomputing.
MEMOIZED-CUT-ROD(p, n):
let r[0..n] be a new array, initialized to -infinity
return MEMOIZED-CUT-ROD-AUX(p, n, r)
MEMOIZED-CUT-ROD-AUX(p, n, r):
if r[n] ≥ 0:
return r[n] // already computed
if n == 0:
q = 0
else:
q = -infinity
for i = 1 to n:
q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
r[n] = q
return qBottom-Up Dynamic Programming
An alternative approach, usually preferred for its simplicity and often better constant factors, solves subproblems in a specific order — smallest first — so that whenever a larger subproblem needs a smaller one, it is already computed.
BOTTOM-UP-CUT-ROD(p, n):
let r[0..n] be a new array
r[0] = 0
for j = 1 to n:
q = -infinity
for i = 1 to j:
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]Both the memoized and bottom-up versions run in Θ(n²) time, a dramatic improvement over the exponential naive recursion, since each of the n+1 subproblems is solved exactly once, and each solution requires O(n) work in the worst case.
A More Complex Example: Matrix-Chain Multiplication
Consider multiplying a chain of matrices A₁ × A₂ × ... × Aₙ. Matrix multiplication, discussed earlier in this series, is associative, so the result is the same regardless of parenthesization, but the number of scalar multiplications required can vary enormously depending on the order in which the multiplications are performed.
Example: A₁ (10×100), A₂ (100×5), A₃ (5×50)
Parenthesization ((A₁A₂)A₃):
A₁A₂ costs 10·100·5 = 5,000 multiplications, result is 10×5
(A₁A₂)A₃ costs 10·5·50 = 2,500 multiplications
Total: 7,500 multiplications
Parenthesization (A₁(A₂A₃)):
A₂A₃ costs 100·5·50 = 25,000 multiplications, result is 100×50
A₁(A₂A₃) costs 10·100·50 = 50,000 multiplications
Total: 75,000 multiplicationsThe difference is a factor of 10 for just three matrices — the gap grows dramatically larger for longer chains, making the choice of parenthesization critically important for performance.
Defining the Recursive Structure
Let m[i][j] denote the minimum number of scalar multiplications needed to compute the product Aᵢ...Aⱼ. The key recursive idea is to consider every possible position k where the final multiplication (the "outermost" split) could occur.
m[i][j] = 0 if i == j
m[i][j] = min over k (i ≤ k < j) of:
m[i][k] + m[k+1][j] + pᵢ₋₁·pₖ·pⱼ
where pᵢ₋₁, pᵢ are the dimensions of matrix AᵢThis recurrence says: for some split point k, first optimally compute the product of the left part Aᵢ...Aₖ, then optimally compute the product of the right part Aₖ₊₁...Aⱼ, then multiply these two resulting matrices together, and choose whichever k minimizes the total.
Bottom-Up Computation
Since m[i][j] depends on subproblems involving shorter chains, the computation proceeds by chain length, from length 1 up to the full chain length n.
MATRIX-CHAIN-ORDER(p, n):
let m[1..n][1..n] and s[1..n][1..n] be new tables
for i = 1 to n:
m[i][i] = 0
for length = 2 to n:
for i = 1 to n - length + 1:
j = i + length - 1
m[i][j] = infinity
for k = i to j - 1:
cost = m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j]
if cost < m[i][j]:
m[i][j] = cost
s[i][j] = k // remember the optimal split
return m, sThe table s[i][j] records the optimal split point, allowing the actual optimal parenthesization to be reconstructed afterward. This algorithm runs in Θ(n³) time: there are Θ(n²) entries in the table, and each takes O(n) time to compute by trying every possible split point.
The Two Essential Properties for Dynamic Programming
Both examples above share two properties that, together, indicate when dynamic programming is the right technique for a given optimization problem.
Optimal Substructure
A problem exhibits Optimal Substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. In rod cutting, the optimal way to cut a rod of length n incorporates an optimal solution for the remaining length after the first cut. In matrix-chain multiplication, the optimal parenthesization of the full chain incorporates optimal parenthesizations of the left and right sub-chains at the chosen split point.
Proving optimal substructure typically follows a "cut-and-paste" argument: assume some solution exists that uses a suboptimal solution to a subproblem, then show that replacing that piece with the true optimal solution to the subproblem cannot make the overall solution worse, contradicting the assumption that it was optimal or showing the improved solution is at least as good.
Overlapping Subproblems
A problem has Overlapping Subproblems when a naive recursive algorithm revisits the exact same subproblems repeatedly, rather than always generating brand-new subproblems, as would be the case in a typical divide-and-conquer algorithm like merge sort. This is precisely why storing subproblem solutions, either through memoization or a bottom-up table, provides such a dramatic speedup: without overlapping subproblems, there would be nothing to gain from caching results.
Why These Two Properties Matter for Recognizing New Problems
When facing a new optimization problem, checking for these two properties is the standard diagnostic for whether dynamic programming is an appropriate technique. If a problem has optimal substructure but its subproblems do not overlap (each recursive call generates genuinely distinct subproblems), divide-and-conquer, discussed earlier in this series, is typically the more natural and equally efficient approach. It is specifically the combination of optimal substructure and significant subproblem overlap that makes dynamic programming's memoization or tabulation strategy pay off with an asymptotic improvement over naive recursion.