Principles of Dynamic Programming

Dynamic programming is one of the most broadly applicable 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: 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 but exponentially slow.

It is slow because it recomputes the same values exponentially many 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.

def recursive_fibonacci(index: int) -> int:
  """
    F(index) by the naive recurrence, recomputing every subproblem.\n
    Correct but Theta(phi^index) time — present only as the disaster to cure.\n
  """
  if index < 2:
    return index
  return recursive_fibonacci(index - 1) + recursive_fibonacci(index - 2)

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.

from typing import Optional


def memoized_fibonacci(
  index: int,
  memo: Optional[dict[int, int]] = None,
) -> int:
  """
    F(index) top-down: recurse as before but cache each answer the first\n
    time it is computed. Every later request is a single lookup, so the\n
    running time drops to Theta(index).\n
  """
  if memo is None:
    memo = {}

  # return the cached answer if this subproblem was already solved.
  cached: Optional[int] = memo.get(index)
  if cached is not None:
    return cached

  # otherwise compute, store, and return F(index).
  result: int = (
    index
    if index < 2
    else memoized_fibonacci(index - 1, memo)
    + memoized_fibonacci(index - 2, memo)
  )
  memo[index] = result
  return result

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.

def tabulated_fibonacci(index: int) -> int:
  """
    F(index) bottom-up: fill a table F[0..index] in increasing order, so\n
    every dependency is ready before it is needed. No recursion, no memo\n
    overhead. Theta(index) time and Theta(index) space.\n
  """
  if index < 2:
    return index

  # seed the base cases, then fill each entry from its two predecessors.
  table: list[int] = [0 for _ in range(index + 1)]
  table[1] = 1
  for position in range(2, index + 1):
    table[position] = table[position - 1] + table[position - 2]

  return table[index]


def rolling_fibonacci(index: int) -> int:
  """
    F(index) in Theta(1) space: since F[i] depends only on the previous two\n
    entries, the whole table collapses to two scalars.\n
  """
  if index < 2:
    return index

  # roll the last two values forward, discarding everything older.
  previous: int = 0
  current: int = 1
  for _ in range(2, index + 1):
    previous, current = current, previous + current

  return current

The two conditions that make DP work

Dynamic programming 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. The method distils into an explicit checklist, the key steps in a DP solution, and every example follows the same order.

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

Deriving the four ingredients

Four decisions turn a problem into a dynamic program: the state, the recurrence, the base case, and the evaluation order. They are not independent guesses; each one constrains the next.

• State. Ask what a subproblem needs to know about the past to make its next decision. Every piece of that information becomes an index. Rod cutting needs only the remaining length, so one index $i$ suffices; if a second parameter (a budget, a previous choice, a position in a second string) also mattered, the state would grow a second index. The rule of thumb: the state must be a sufficient summary — two inputs that lead to the same future optimum should map to the same state.
• Recurrence. Fix the state, then name the first (or last) decision an optimal solution makes and enumerate its possible values. Each value leaves a smaller instance whose optimum you already trust; combine the immediate reward with that optimum and take the best. Interval scheduling has one binary decision (take $I_i$ or not); rod cutting has $i$ decisions (the length of the rightmost piece).
• Base case. Read it off the smallest states where no decision remains — the empty rod, the empty interval prefix — usually a value of $0$ or $1$.
• Evaluation order. Any linear order in which every state precedes the states that depend on it works. When the state is a single index and the recurrence reaches only smaller indices, plain increasing order suffices; multi-index states fill in the order of a topological sort of the dependency DAG.

A worked optimization: weighted interval scheduling

Fibonacci shows the speedup but not the optimization structure that DP is mostly used for. 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 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.

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 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)$.

Step 7: Correctness of the pseudocode. The loop is a faithful transcription of the DP equation: at iteration $i$ it reads $\text{Opt}[i-1]$ and $\text{Opt}[q(i)]$, takes the larger of the exclude value and $p_i$ plus the include value, and stores it in $\text{Opt}[i]$. Both entries it reads were filled on an earlier iteration, since $i-1<i$ and $q(i)<i$, so the increasing-$i$ order respects every dependency. Composed with the Step 4 induction, each $\text{Opt}[i]$ holds the true optimum, and $\text{Opt}[n]$ is the answer.

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.

from bisect import bisect_right
from typing import NamedTuple, Sequence

class Interval(NamedTuple):
  """
    One job: a half-open span [start, finish) and the profit it earns.\n
  """
  start: int
  finish: int
  profit: int

def _compatible_predecessors(
  intervals: Sequence[Interval],
) -> list[int]:
  """
    For intervals sorted by finish time, return q where q[i] is the count of\n
    earlier intervals entirely left of intervals[i] (so indices 0..q[i]-1 are\n
    compatible with it). Found by binary search on the sorted finish times.\n
  """
  # each q[i] counts earlier intervals whose finish <= this one's start.
  finish_times: list[int] = [interval.finish for interval in intervals]
  return [
    bisect_right(finish_times, interval.start) for interval in intervals
  ]

def max_profit_schedule(intervals: Sequence[Interval]) -> int:
  """
    The maximum total profit of a pairwise-disjoint subset of `intervals`.\n
    Two intervals are disjoint when one finishes at or before the other\n
    starts (spans are half-open).\n
  """
  if not intervals:
    return 0

  # sort by finish time, then precompute the compatible-predecessor of each.
  ordered: list[Interval] = sorted(intervals, key=lambda job: job.finish)
  predecessors: list[int] = _compatible_predecessors(ordered)

  # best_profit[i] = max profit using only the first i intervals.
  best_profit: list[int] = [0 for _ in range(len(ordered) + 1)]
  for index, interval in enumerate(ordered, start=1):
    take: int = interval.profit + best_profit[predecessors[index - 1]]
    skip: int = best_profit[index - 1]
    best_profit[index] = max(skip, take)

  return best_profit[len(ordered)]

def optimal_schedule(intervals: Sequence[Interval]) -> list[Interval]:
  """
    An actual maximum-profit disjoint subset, recovered by recording the\n
    winning choice at each entry and tracing it back from the last interval.\n
  """
  if not intervals:
    return []

  # sort by finish time, then precompute the compatible-predecessor of each.
  ordered: list[Interval] = sorted(intervals, key=lambda job: job.finish)
  predecessors: list[int] = _compatible_predecessors(ordered)

  # fill the table, recording at each entry whether taking interval i won.
  best_profit: list[int] = [0 for _ in range(len(ordered) + 1)]
  chosen: list[bool] = [False for _ in range(len(ordered) + 1)]
  for index, interval in enumerate(ordered, start=1):
    take: int = interval.profit + best_profit[predecessors[index - 1]]
    skip: int = best_profit[index - 1]
    best_profit[index] = max(skip, take)
    chosen[index] = take > skip

  # walk back: take interval index, jump to its compatible predecessor.
  selection: list[Interval] = []
  index = len(ordered)
  while index > 0:
    if chosen[index]:
      selection.append(ordered[index - 1])
      index = predecessors[index - 1]
    else:
      index -= 1

  selection.reverse()
  return selection

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.

Filling the table by hand. With the price list above, the loop fills $\text{Opt}[\mathrm{0..8}]$ from left to right. Each entry takes the best over every rightmost piece length $j$; the winning $j$ is what $\text{rightmost}[i]$ records for the reconstruction pass.

Read one entry to see the enumeration. For $i=4$ the four candidates are

won by $j=2$, so $\text{rightmost}[4]=2$: cut a length-$2$ piece and solve the length-$2$ remainder optimally. Every entry to the right reuses the entries to its left — $\text{Opt}[3],\text{Opt}[2],\text{Opt}[1],\text{Opt}[0]$ each feed several later rows, which is the overlap that makes the table pay off.

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

from typing import Sequence

def max_revenue(prices: Sequence[int], length: int) -> int:
  """
    The maximum revenue obtainable from a rod of `length`, where\n
    `prices[piece - 1]` is the price of a piece of size `piece`.\n
    `length` must not exceed `len(prices)`.\n
  """
  # best_revenue[s] = most revenue from a length-s rod, built bottom-up.
  best_revenue: list[int] = [0 for _ in range(length + 1)]
  for size in range(1, length + 1):

    # try every length for the rightmost piece, keep the best total.
    for piece in range(1, size + 1):
      candidate: int = prices[piece - 1] + best_revenue[size - piece]
      best_revenue[size] = max(best_revenue[size], candidate)

  return best_revenue[length]

def optimal_cuts(prices: Sequence[int], length: int) -> list[int]:
  """
    A list of piece lengths summing to `length` that earns `max_revenue`,\n
    recovered by storing the winning rightmost piece at each size and\n
    following it back down to zero.\n
  """
  # fill the revenue table, recording the winning rightmost piece per size.
  best_revenue: list[int] = [0 for _ in range(length + 1)]
  rightmost: list[int] = [0 for _ in range(length + 1)]
  for size in range(1, length + 1):
    for piece in range(1, size + 1):
      candidate: int = prices[piece - 1] + best_revenue[size - piece]
      if candidate > best_revenue[size]:
        best_revenue[size] = candidate
        rightmost[size] = piece

  # follow the recorded pieces back down to a length of zero.
  cuts: list[int] = []
  remaining: int = length
  while remaining > 0:
    cuts.append(rightmost[remaining])
    remaining -= rightmost[remaining]

  return cuts

The overlap that makes tabulation worthwhile is visible in the subproblem dependency graph. Each length depends on every shorter length, so the low-index entries are reused again and again — a naive recursion would recompute each of them an exponential number of times, while the table computes each once.

Common pitfalls

A handful of mistakes account for most broken dynamic programs.

• A state that is not a sufficient summary. If two instances with the same state can have different optimal futures, the recurrence is unsound: the table entry conflates cases that should be distinguished. To address this, add the missing parameter to the state, even at the cost of a larger table.
• An evaluation order that reads unfilled cells. Bottom-up code that visits states before their dependencies computes on garbage. Always confirm that the recurrence for a state reaches only states that come earlier in the fill order.
• Confusing optimal substructure with greedy choice. Optimal substructure says the sub-solutions are optimal, not that a locally best first move is globally best. Rod cutting enumerates every first piece precisely because no single greedy cut is always right.
• Assuming DP where subproblems do not overlap. Merge sort splits into disjoint halves; memoizing it caches entries that are each hit once, so it gains nothing over plain divide-and-conquer. DP helps only when the same subproblem recurs.
• Forgetting the reconstruction bookkeeping. Computing the optimal value is half the job; if the problem asks for the optimal object, record the winning choice at each state (as $\text{chosen}$ and $\text{rightmost}$ do) so the trace-back can rebuild it.

Where the name and the method come from

The name dynamic programming is a historical accident worth knowing. Richard Bellman coined it in the 1950s at RAND while working on multistage decision processes; programming meant planning (as in linear programming), not writing code, and Bellman later admitted in his autobiography that he chose dynamic partly because it was impossible to use pejoratively and would shield the research from a skeptical Secretary of Defense. The mathematical core is Bellman's principle of optimality — an optimal policy has the property that whatever the initial state and decision, the remaining decisions must be optimal with respect to the state that results — the optimal-substructure condition itself, stated for sequential decision problems. Bellman's Dynamic Programming (1957) is the founding text.⁴

That decision-process lineage leads directly to reinforcement learning. The Bellman equation $V(s)={\max }_a(r(s,a)+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)V(s^{\prime }))$ is the infinite-horizon, probabilistic generalization of the recurrences in this lesson — value iteration is tabulation, and the whole field of approximate dynamic programming exists because the state space is too large to fill a table (Bertsekas, Dynamic Programming and Optimal Control). The number of subproblems $\times$ work per subproblem cost model also has a modern lower-bound counterpart: for some classic DPs the quadratic running time is provably near-optimal. Backurs and Indyk (2015) showed that edit distance and several sequence DPs cannot be solved in strongly subquadratic $O(n^{2-\epsilon })$ time unless the Strong Exponential Time Hypothesis fails — so the $\Theta (mn)$ table of the next lesson is essentially the best one can hope for.

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)$.