Dynamic Programming Foundations: Rod Cutting, Matrix Chains, and Core Principles

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 20

A 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 q

This 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 q

Bottom-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 multiplications

The 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, s

The 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.