Principles of Dynamic Programming

Dynamic programming is one of the most powerful and most misunderstood ideas in algorithm design. The name, coined by Richard Bellman in the 1950s, is a historical accident: it has nothing to do with dynamics and little to do with programming in the modern sense. Erickson gives a one-line definition that cuts through the mystique: dynamic programming is recursion without repetition.¹ We find a recursive structure for the problem, notice that the naive recursion solves the same subproblems over and over, and then arrange to solve each distinct subproblem exactly once, remembering its answer.

That single move, trading repeated computation for stored results, can collapse an exponential running time to a polynomial one. The rest is bookkeeping: identifying the subproblems, writing the recurrence that relates them, and deciding the order in which to fill in the answers.

A motivating disaster: Fibonacci

The Fibonacci numbers are defined by the recurrence

Transcribed directly into a recursive procedure, this definition is correct and catastrophically slow.

Why is it slow? Because it recomputes the same values an astronomical number of times. The recursion tree for $F(5)$ shows the waste already:

The subtree rooted at $F_3$ appears twice; $F_2$ appears three times; and the duplication compounds with depth. The number of leaves is itself $\Theta (F(n))$, and since the Fibonacci numbers grow like ${\varphi }^n$ (with $\varphi =(1+\sqrt{5})/2\approx 1.618$ the golden ratio), $\text{Rec-Fib}$ runs in $\Theta ({\varphi }^n)$ time: exponential, to compute a quantity we could write down in a fraction of a second.

The diagnosis is precise: there are only $n+1$ distinct subproblems, $F(0),F(1),\dots ,F(n)$, but the recursion visits them exponentially often.

The first cure: memoization (top-down)

The minimal fix keeps the recursive structure but adds a memo, a table that remembers each answer the first time we compute it. Before recursing, we check the table; if the answer is there, we return it immediately.

Now each of the $n+1$ subproblems is solved once; every later request for it is a single table lookup. The running time drops from exponential to $\Theta (n)$. This style, recurse as before but cache results, is called memoization (note: memo-ization, not memorization). It is the top-down form of dynamic programming, and it is often the easiest to write, because it is just the natural recursion plus a guard.²

Compare the recursion tree now against the naive one above: every repeated subproblem becomes a cache hit that returns at once, so the exponential tree collapses to a thin spine of $n+1$ first-time computations.

The greyed nodes ($F_3$, $F_2$, $F_1$) are the duplicates from the naive tree; here they resolve in a single lookup, so the whole computation touches each of $F_0,\dots ,F_5$ exactly once.

The second cure: tabulation (bottom-up)

If we know in advance which subproblems we need and in what order their dependencies resolve, we can drop the recursion entirely and fill the table directly with a loop. This is tabulation, the bottom-up form.

The loop visits subproblems in an order, $0,1,2,\dots ,n$, that guarantees every dependency is ready before it is needed. No recursion, no memo-check overhead, no risk of stack overflow.

The two cures fill the same array; they differ only in the order they visit its cells. Bottom-up sweeps the indices forward; top-down dives to $F_n$ first and writes each cell as the recursion unwinds.

The two conditions that make DP work

Dynamic programming is not a universal hammer. It applies precisely when a problem has two structural properties, both emphasized by all three texts.

1. Overlapping subproblems. The recursive solution revisits the same subproblems repeatedly; there are only polynomially many distinct ones, even though the naive recursion calls them exponentially often. This is what makes caching pay off. (Contrast divide-and-conquer like merge sort, where each recursive call is on a fresh subproblem; there is nothing to cache, so memoization buys nothing.)

2. Optimal substructure. An optimal solution to the problem is built from optimal solutions to its subproblems. This is what lets us write a recurrence at all: we can express the best answer for an instance in terms of the best answers for smaller instances. CLRS states the test sharply: cut an optimal solution at some choice point; the piece that remains must itself be an optimal solution to the residual subproblem, or we could splice in a better piece and improve the whole, a contradiction.³

The dynamic-programming recipe

DP is a design discipline, not a bag of tricks. The method distils into an explicit checklist, the key steps in a DP solution, and every example follows the same order. Following it turns a moment of insight into a routine you can execute.

1. Identify a simplified goal (maybe). Often the original problem asks for an optimal object (the actual set of cuts, the actual chosen intervals). First solve the easier problem of computing only the optimal value; recovering the object is a separate, usually short, step at the end.
2. Clearly define the subproblems; set up notation. State precisely what quantity $\text{Opt}(\cdot )$ denotes, in one English sentence, and which call gives the final answer. This is the single hardest and most important step. Get the subproblem definition right and everything else follows; get it wrong and nothing will.
3. Write the DP equations. Express $\text{Opt}$ of a subproblem in terms of $\text{Opt}$ of smaller subproblems, together with the base case(s). This is where optimal substructure is used: enumerate the choices an optimal solution could make at its first decision point and take the best.
4. Prove correctness of the equations (induction, usually). Argue by induction on subproblem size that the equation computes exactly the quantity the definition names.
5. Write the pseudocode (be iterative!). Turn the equations into a bottom-up loop that fills a table in an order respecting the dependencies.
6. Get back to the original goal (maybe). If a simplified goal was used, reconstruct the optimal object, either by storing the winning choice at each entry, or by tracing back through the filled table.
7. Argue correctness of the pseudocode (usually very short): it faithfully evaluates the equations in a valid order.
8. Analyze the running time. Almost mechanical: it is the number of subproblems times the work per subproblem (the time to evaluate one line of the recurrence).

The rest of this lesson runs the recipe end-to-end on two opening examples: first weighted interval scheduling, then rod cutting.

A worked optimization: weighted interval scheduling

Fibonacci shows the speedup but hides the optimization flavor that gives DP its real power. The first optimization example is weighted interval scheduling, which sharpens the greedy interval-scheduling problem you have already met: now each interval carries a profit, and we want the most profitable compatible set rather than merely the most intervals.

Input. Intervals $⟨I_1,\dots ,I_n⟩$, each $I_i=(s_i,f_i)$ with a profit $p_i$. Desired output. A subset $\left\{I_{i_1},\dots ,I_{i_k}\right\}$ that is feasible (the chosen intervals are pairwise disjoint) and maximizes $p_{i_1}+\cdots +p_{i_k}$.

Step 1: Simplified goal. Compute only the maximum achievable profit $\text{Opt}(I_1,\dots ,I_n)$; we recover the actual subset afterwards.

Step 2: Subproblems and notation. The key preprocessing move is to sort the intervals by increasing finish time, so $f_1\le f_2\le \cdots \le f_n$. Once sorted, every subproblem we ever need has the contiguous prefix form $⟨I_1,\dots ,I_i⟩$, so a single index $i$ names it. Define

and we want $\text{Opt}(n)$. For each $i$ we also precompute

the index of the rightmost interval to the left of $I_i$ that does not overlap $I_i$ (and $q(i)=0$ if none exists). Because finish times are sorted, $I_j$ ends before $I_i$ starts is exactly the test, so $q(i)$ is well defined.

Drawn on a timeline, the intervals stack up by finish time, and $q(i)$ is just the last bar that clears $I_i$'s left edge:

Step 3: DP equations. Consider the last interval $I_i$ and make one binary choice — include it or not:

If we exclude $I_i$, the best we can do is $\text{Opt}(i-1)$. If we include it, we collect $p_i$ and may no longer use any interval that overlaps $I_i$; the remaining usable intervals are exactly $⟨I_1,\dots ,I_{q(i)}⟩$, so we add $\text{Opt}(q(i))$ — optimal substructure in action.

Step 4: Correctness (sketch). By induction on $i$. The base case $\text{Opt}(0)=0$ is immediate. For the step, any optimal schedule on the first $i$ intervals either omits $I_i$ (an optimal schedule on the first $i-1$, by the inductive hypothesis $=\text{Opt}(i-1)$) or contains $I_i$ (then the rest is an optimal schedule on $⟨I_1,\dots ,I_{q(i)}⟩$, contributing $p_i+\text{Opt}(q(i))$). Taking the max of the two cases is exactly the equation.

Step 5: Pseudocode. Fill the table in increasing $i$, so both $\text{Opt}[i-1]$ and $\text{Opt}[q(i)]$ are ready when needed.

Step 8: Running time. The sort costs $O(n\log n)$. Each of the $n$ table entries does $O(1)$ work given $q(i)$. The values $q(i)$ themselves can be found by binary search ($O(\log n)$ each) or, since they are monotone in $i$, by a single linear scan that advances across all iterations in $O(n)$ total. Either way the sort dominates, for a worst-case running time of

This is the canonical include-or-exclude DP, and its dependency structure makes the overlap concrete: entry $\text{Opt}(i)$ points back to its two predecessors, $\text{Opt}(i-1)$ and $\text{Opt}(q(i))$, and those arrows cross and reconverge on shared subproblems, the same overlap that doomed naive Fibonacci.

Several nodes ($\text{Opt}(2)$, $\text{Opt}(1)$, $\text{Opt}(0)$) are pointed to more than once: those are the overlapping subproblems the table solves just once.

Step 6: Back to the original goal. To recover the actual set, record at each $i$ which branch won. In the pseudocode below, $\text{chosen}[i]=\text{true}$ means $I_i$ is in the optimal solution for the prefix $⟨I_1,\dots ,I_i⟩$.

Trace back from $i=n$: if $\text{chosen}[i]$, output $I_i$ and jump to $q(i)$; otherwise step to $i-1$. This walk recovers an optimal set in $O(n)$.

A second worked optimization: rod cutting

The same recipe applied to rod cutting (CLRS's opening case) shows a different flavor of choice — not binary, but try every first piece. Given a rod of integer length $n$ and a price $p_i$ for a piece of length $i$, cut the rod into integer pieces to maximize total revenue. With the price table

a rod of length $n=8$ sells whole for $20$, but cutting it as $6+2$ earns $17+5=22$ — so the cuts matter.

Simplified goal. Find just the maximum obtainable revenue. Subproblem. Let $\text{Opt}(i)$ be the max revenue from a rod of length $i$; we want $\text{Opt}(n)$. DP equations. Consider the rightmost cut. If the rightmost piece has length $j$ (for some $1\le j\le i$), we earn $p_j$ and cut the remaining length $i-j$ optimally — optimal substructure. We do not know the best $j$, so we try them all:

The subproblems $\text{Opt}(0),\dots ,\text{Opt}(n)$ are ordered by length, so we fill them in increasing order.

Running time. There are $n$ subproblems, and the work to compute $\text{Opt}[i]$ is at most $bi$ for a constant $b$ (the inner loop runs $i$ times). Summing,

a polynomial replacement for the $\Theta (2^{n-1})$ ways to cut the rod that a naive recursion would explore. To recover the cuts, store the winning length $j$ in a second array $\text{rightmost}[i]$, then read them off by following $n\to n-\text{rightmost}[n]\to \cdots \to 0$.

Takeaways

• Dynamic programming is recursion without repetition: find a recursive structure, then solve each distinct subproblem once and store the result.
• It applies exactly when the problem has overlapping subproblems (so caching helps) and optimal substructure (so a recurrence over subproblems is correct).
• Memoization (top-down) caches results inside the natural recursion; tabulation (bottom-up) fills the table with a loop in dependency order. Same values, same time; tabulation often saves space.
• The DP recipe develops every dynamic program systematically: simplified goal → define subproblems/notation → DP equations → prove correctness by induction → iterative pseudocode → recover the original object → runtime.
• The hardest step is defining the subproblem; a smart preprocessing choice can make it cheap: sorting intervals by finish time reduces every subproblem to a prefix named by one index.
• Running time $=$ (number of subproblems) $\times$ (work per subproblem): Fibonacci becomes $\Theta (n)$, weighted interval scheduling $O(n\log n)$, rod cutting $\Theta (n^2)$.