Dynamic Programming: Memoization, Tabulation, and Rod Cutting

Understand dynamic programming as a distinct technique from divide-and-conquer — it applies when a recursive breakdown of a problem produces overlapping subproblems (the same subproblem size gets solved repeatedly across different call paths) rather than fresh, disjoint ones. CLRS frames this as a four-step recipe: characterize the structure of an optimal solution, recursively define its value, compute that value bottom-up, and (optionally) reconstruct the actual solution from the table. Rod cutting — CLRS's own running example — makes the payoff concrete: the same problem goes from exponential-time naive recursion to a quadratic-time table fill, just by making sure each subproblem is solved once instead of over and over.

• Any optimization problem built from a choice that leaves behind a smaller instance of the same problem — cutting stock/rods, coin change, knapsack, edit distance — where the naive recursive solution visibly redoes the same work.
• Recognizing, before writing any code, whether a problem is a divide-and-conquer candidate (subproblems disjoint — mergesort's two halves never overlap) or a dynamic-programming candidate (subproblems overlap — the same smaller rod length is needed by many different larger cuts).
• Choosing between top-down (memoized recursion, easier to derive directly from the recurrence) and bottom-up (tabulation, usually faster in practice, no call-stack overhead) once you've confirmed a problem has the DP hallmarks.

Why overlapping subproblems break plain recursion: CUT-ROD's exponential blowup

Serling Enterprises has a price table p[i] for a rod of length i, and wants the maximum revenue r[n] obtainable by cutting a length-n rod into pieces and selling them (cuts are free). The direct recursive translation of the recurrence r[n] = max(p[i] + r[n-i]) for 1 <= i <= n is CLRS's CUT-ROD:

java
static int cutRod(int[] p, int n) {
    if (n == 0) return 0;
    int q = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        q = Math.max(q, p[i] + cutRod(p, n - i));
    }
    return q;
}

This is correct, and it is also exponential in n — CLRS notes that once n reaches the 30s or 40s, it takes minutes to hours, roughly doubling every time n increases by one. The reason: cutRod(p, n) calls cutRod(p, n - i) for every i from 1 to n, which is the same as calling cutRod(p, j) for every j from 0 to n - 1 — and each of those calls does the same thing again. The same subproblem size gets re-solved from scratch every time it's needed, instead of once.

Instrumenting the naive version to count calls per subproblem size makes the blowup visible instead of just asserted:

java
static int[] callsBySize = new int[5]; // index = rod length being solved

static int cutRodCounted(int[] p, int n) {
    callsBySize[n]++;
    if (n == 0) return 0;
    int q = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        q = Math.max(q, p[i] + cutRodCounted(p, n - i));
    }
    return q;
}

Running cutRodCounted(p, 4) and printing callsBySize afterward:

plaintext
rod length solved:    4    3    2    1    0
number of calls:      1    1    2    4    8      (16 calls total)

A single call to solve length 4 triggers 16 recursive calls in total — and the length-0 base case alone is recomputed 8 separate times, length-1 four times, length-2 twice. CLRS's recursion tree (Figure 14.3) shows exactly this shape for n = 4: the count of calls needed to solve a rod of length n, T(n), satisfies T(0) = 1 and T(n) = 1 + sum(T(j) for j = 0..n-1), which works out to T(n) = 2^n — genuinely exponential, and it's exponential specifically because the recursion keeps revisiting subproblem sizes it has already solved, not because the problem itself demands exponentially many distinct pieces of work.

Memoization: cache each subproblem's answer, compute it exactly once

The recursive structure of CUT-ROD doesn't need to change to fix this — only its bookkeeping does. Top-down memoization keeps the same shape but checks a cache before doing any work, and writes to that cache before returning:

java
static int memoizedCutRod(int[] p, int n) {
    int[] r = new int[n + 1];
    Arrays.fill(r, -1); // -1 marks "not yet solved" (revenue is always >= 0)
    return memoizedCutRodAux(p, n, r);
}

static int memoizedCutRodAux(int[] p, int n, int[] r) {
    if (r[n] >= 0) return r[n];          // already solved this size — just look it up
    int q;
    if (n == 0) {
        q = 0;
    } else {
        q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + memoizedCutRodAux(p, n - i, r));
        }
    }
    r[n] = q;   // remember it — every future call for this size returns in O(1)
    return q;
}

With the cache in place, the very first time memoizedCutRodAux is asked for rod length 2, it does the full computation and stores the answer in r[2]. Every subsequent call for length 2 — and in the n = 4 tree above, there were two of them — hits the r[n] >= 0 check and returns immediately. Each distinct subproblem size from 0 to n is computed exactly once; every other visit is a constant-time lookup. That turns the Θ(2^n) naive recursion into Θ(n^2): n + 1 distinct subproblems, each doing up to n units of work in its for loop.

Bottom-up tabulation: fill the table in dependency order, smallest first

The recursive structure and the cache together are really just an indirect way of saying "solve subproblems smallest first, and remember their answers." Tabulation does that directly, with no recursion at all: an ordinary loop fills r[0..n] in increasing order of rod length, so that by the time the loop needs r[j - i] to help compute r[j], it has already been filled in.

java
static int bottomUpCutRod(int[] p, int n) {
    int[] r = new int[n + 1];
    r[0] = 0; // a rod of length 0 earns no revenue
    for (int j = 1; j <= n; j++) {         // solve subproblems smallest-first
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= j; i++) {
            q = Math.max(q, p[i] + r[j - i]);  // r[j - i] is already filled in
        }
        r[j] = q;
        printTableSoFar(r, j);
    }
    return r[n];
}

Using CLRS's own sample price table (p[1..10] = 1, 5, 8, 9, 10, 17, 17, 20, 24, 30), printing the table's contents after processing rod lengths 2, 6, and 10 shows the array actually filling in, left to right, each entry depending only on entries already to its left:

After j = 2:

length i	0	1	2
r[i]	0	1	5

After j = 6:

length i	0	1	2	3	4	5	6
r[i]	0	1	5	8	10	13	17

After j = 10 (final):

length i	0	1	2	3	4	5	6	7	8	9	10
r[i]	0	1	5	8	10	13	17	18	22	25	30

r[4] = 10 confirms the optimal cut for a length-4 rod is two 2-inch pieces (p[2] + p[2] = 5 + 5 = 10), beating selling it uncut (p[4] = 9) — and it was computed using r[2], which the loop had already filled in two iterations earlier. Both memoization and tabulation run in Θ(n^2) — CLRS notes tabulation usually wins on constant factors in practice, since it has no procedure-call overhead, while memoization's advantage is that it falls out directly from the recurrence with less restructuring.

The two hallmarks: when dynamic programming actually applies

CLRS names exactly two properties an optimization problem must have for dynamic programming to be a viable technique:

• Optimal substructure — an optimal solution to the problem contains within it optimal solutions to subproblems. For rod cutting: if cutting a length-n rod optimally involves any cut at all, the piece left over after that first cut must itself be cut optimally — if it weren't, splicing in a better solution to the remainder would beat the supposedly-optimal original, a contradiction.
• Overlapping subproblems — a recursive algorithm for the problem revisits the same subproblem sizes repeatedly, rather than generating fresh ones at every step, and the total number of distinct subproblems is polynomial in the input size. This is exactly what the callsBySize trace above demonstrates: only 5 distinct rod lengths (0-4) exist as subproblems, but the naive recursion solves them 16 times combined.

This is precisely the property that separates dynamic programming from divide-and-conquer. CLRS states it directly: divide-and-conquer "partitions the problem into disjoint subproblems, solves the subproblems recursively, and then combines their solutions" — mergesort's left half and right half never share any sub-subproblem, so there's nothing to cache and no benefit to memoizing. Dynamic programming applies precisely when that disjointness breaks down: "a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems." Optimal substructure alone isn't sufficient, either — CLRS's counterexample is unweighted longest simple path, which has optimal-substructure-shaped subproblems that turn out not to be independent (splicing two locally-optimal subpaths together can revisit a vertex and produce an illegal, non-simple path), and no efficient DP solution for it is known.

• Memoization vs. tabulation is a real engineering choice, not just style — memoization is often the smaller diff from a brute-force recursive solution (add a cache, check it, populate it) and naturally skips subproblems the top-down call pattern never actually needs; tabulation guarantees you visit every subproblem in dependency order with no recursion-stack depth risk and typically lower constant factors, at the cost of committing to solve the entire subproblem space up front.
• Dynamic programming is fundamentally a time-memory trade-off, and CLRS says so explicitly — the extra Θ(n) array (or Θ(n^2) table, for two-dimensional problems like matrix-chain multiplication) is the price paid to convert exponential time into polynomial time. For a rod-cutting instance where n is genuinely huge, that memory cost is itself worth checking, not just assumed to be free.
• Both hallmarks are required — optimal substructure without overlapping subproblems means DP buys you nothing: if every recursive call in a correct divide-and-conquer algorithm produces subproblems no other call will ever need again (mergesort's halves), a cache sits there unused and adds only overhead. Confirm a recursive solution is actually revisiting subproblem sizes (as the callsBySize trace shows for rod cutting) before reaching for a cache.
• Needing the actual solution, not just its value, costs another table — memoizedCutRod/bottomUpCutRod above return only the optimal revenue r[n]; reconstructing which cuts produced it means also tracking a parallel s[] array recording the choice made at each subproblem (CLRS's EXTENDED-BOTTOM-UP-CUT-ROD), which is easy to bolt on but easy to forget if the problem statement quietly needs "how", not just "how much".