---
title: Principles of Dynamic Programming
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 1
order: 801
summary: |
  Dynamic programming is recursion with memory: when a recursive solution
  re-solves the same subproblems again and again, we solve each one once and
  store the answer. We identify the two structural conditions that make this
  work — overlapping subproblems and optimal substructure — contrast top-down
  memoization with bottom-up tabulation, and distil the whole method into a
  five-step recipe.
topics: [Dynamic Programming, Recurrences]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming"
  - book: Skiena
    ref: "§10 — Dynamic Programming"
  - book: Erickson
    ref: "Ch. 3 — Dynamic Programming"
practice:
  - title: 'Climbing Stairs'
    slug: climbing-stairs
    difficulty: Easy
  - title: 'Fibonacci Number'
    slug: fibonacci-number
    difficulty: Easy
  - title: 'Min Cost Climbing Stairs'
    slug: min-cost-climbing-stairs
    difficulty: Easy
  - title: 'House Robber'
    slug: house-robber
    difficulty: Medium
  - title: 'Unique Paths'
    slug: unique-paths
    difficulty: Medium
---

**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_.[^erickson-dp] 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](/algorithms/foundations/recurrences) 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
$$
F(n) =
\begin{cases}
0 & \text{if } n = 0, \\[2pt]
1 & \text{if } n = 1, \\[2pt]
F(n-1) + F(n-2) & \text{if } n \ge 2.
\end{cases}
$$
Transcribed directly into a recursive procedure, this definition is correct but
exponentially slow.

```algorithm
caption: $\textsc{Rec-Fib}(n)$ — naive recursive Fibonacci
number: 1
if $n < 2$ then
  return $n$
return $\textsc{Rec-Fib}(n-1)$ **+** $\textsc{Rec-Fib}(n-2)$
```

It is slow because it recomputes the same values exponentially many
times. The recursion tree for $F(5)$ shows the waste already:

$$
% caption: Recursion tree for $F(5)$, each node coloured by its value — so every
%          repeated subproblem (the same $F_k$ recomputed from scratch) shares one
%          colour, and the duplicated subtrees jump out at a glance.
\begin{tikzpicture}[
  level distance=11mm,
  every node/.style={draw, circle, minimum size=7mm, inner sep=1pt},
  level 1/.style={sibling distance=38mm},
  level 2/.style={sibling distance=19mm},
  level 3/.style={sibling distance=11mm}]
  \definecolor{acc}{HTML}{2348F2}
  % colour every node by its subproblem value: same colour = the SAME F_k recomputed.
  % F_5 / F_4 occur once (plain); F_3 (x2) blue, F_2 (x3) green, F_1 (x5) amber, F_0 (x3) violet.
  \node {$F_5$}
    child {node {$F_4$}
      child {node[fill=acc!25] {$F_3$}
        child {node[fill=green!25] {$F_2$}
          child {node[fill=orange!35] {$F_1$}}
          child {node[fill=violet!22] {$F_0$}}}
        child {node[fill=orange!35] {$F_1$}}}
      child {node[fill=green!25] {$F_2$}
        child {node[fill=orange!35] {$F_1$}}
        child {node[fill=violet!22] {$F_0$}}}}
    child {node[fill=acc!25] {$F_3$}
      child {node[fill=green!25] {$F_2$}
        child {node[fill=orange!35] {$F_1$}}
        child {node[fill=violet!22] {$F_0$}}}
      child {node[fill=orange!35] {$F_1$}}};
\end{tikzpicture}
$$

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 $\phi^n$ (with $\phi = (1+\sqrt5)/2
\approx 1.618$ the golden ratio), $\textsc{Rec-Fib}$ runs in $\Theta(\phi^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.

::impl{algo="fibonacci#recursive_fibonacci"}

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

```algorithm
caption: $\textsc{Memo-Fib}(n)$ — top-down with a memo table $M[0..n]$
number: 2
if $M[n]$ is defined then
  return $M[n]$ // already solved
if $n < 2$ then
  $M[n] \gets n$
else
  $M[n] \gets$ $\textsc{Memo-Fib}(n-1)$ **+** $\textsc{Memo-Fib}(n-2)$
return $M[n]$
```

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.[^skiena-dp]

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.

$$
% caption: Memoized $F(5)$: each distinct subproblem is computed once (solid); later
%          requests are cache hits (grey) that return immediately, pruning the repeated
%          subtrees.
\begin{tikzpicture}[
  level distance=11mm,
  every node/.style={draw, circle, minimum size=7mm, inner sep=1pt, font=\small},
  hit/.style={fill=black!12},
  level 1/.style={sibling distance=38mm},
  level 2/.style={sibling distance=19mm},
  level 3/.style={sibling distance=11mm}]
  \node {$F_5$}
    child {node {$F_4$}
      child {node {$F_3$}
        child {node {$F_2$}
          child {node {$F_1$}}
          child {node {$F_0$}}}
        child {node[hit] {$F_1$}}}
      child {node[hit] {$F_2$}}}
    child {node[hit] {$F_3$}};
\end{tikzpicture}
$$

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.

::impl{algo="fibonacci#memoized_fibonacci"}

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

```algorithm
caption: $\textsc{Tab-Fib}(n)$ — bottom-up over a table $F[0..n]$
number: 3
$F[0] \gets 0$
$F[1] \gets 1$
for $i \gets 2$ to $n$ do
  $F[i] \gets F[i-1] + F[i-2]$
return $F[n]$
```

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.

$$
% caption: Top-down and bottom-up fill the same table $F[0..5]$ in opposite orders, yet
%          produce identical values $0,1,1,2,3,5$.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-1.7,0) {\texttt{bottom-up}};
  \foreach \v/\x in {0/0,1/1,1/2,2/3,3/4,5/5} { \node[cell] at (\x,0) {$\v$}; }
  \foreach \x in {0,...,5} { \node[lbl] at (\x,0.72) {$\x$}; }
  \draw[->, thick, acc] (-0.55,-0.62) -- (5.55,-0.62) node[midway, below, draw=none, font=\footnotesize, acc] {\texttt{f\/ill order 0} $\to$ \texttt{5}};
  \node[lbl] at (-1.7,-2.1) {\texttt{top-down}};
  \foreach \v/\x in {0/0,1/1,1/2,2/3,3/4,5/5} { \node[cell] at (\x,-2.1) {$\v$}; }
  \draw[->, thick, acc] (5.55,-2.72) -- (-0.55,-2.72) node[midway, below, draw=none, font=\footnotesize, acc] {\texttt{recurse from 5, f\/ill on return}};
\end{tikzpicture}
$$

> **Remark (Top-down vs bottom-up).** Top-down and bottom-up compute _exactly the same values_ and have the _same_
> asymptotic running time. Memoization solves only the subproblems actually
> reachable from the top, which can be a win when many subproblems are
> irrelevant; tabulation has lower constant-factor overhead and often exposes a
> space optimization. For Fibonacci, since $F[i]$ depends only on the previous
> two entries, the table can shrink to two scalars, giving $\Theta(1)$ space.

::impl{algo="fibonacci#tabulated_fibonacci+rolling_fibonacci"}

## 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.[^clrs-dp]

> **Fact (When DP applies).** When both hold, dynamic programming applies. When optimal substructure fails,
> no recurrence over subproblems can be correct; when subproblems do not overlap,
> plain divide-and-conquer is already efficient and DP adds only overhead.

## 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 $\textsc{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 $\textsc{Opt}$ of a subproblem in terms of
   $\textsc{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](/algorithms/greedy/the-greedy-method) 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 $\langle I_1, \dots, I_n\rangle$, each $I_i = (s_i, f_i)$
with a profit $p_i$. **Desired output.** A subset $\set{I_{i_1}, \dots, I_{i_k}}$
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
$\textsc{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
$\langle I_1, \dots, I_i\rangle$, so a single index $i$ names it. Define
$$
\textsc{Opt}(i) = \text{max profit obtainable from intervals } \langle I_1, \dots, I_i\rangle,
$$
and we want $\textsc{Opt}(n)$. For each $i$ we also precompute
$$
q(i) = \max\set{\, j : I_j \cap I_i = \emptyset \text{ and } j < i \,},
$$
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:

$$
% caption: Intervals sorted by finish time; $q(i)$ is the rightmost interval ending before
%          $I_i$ starts. Here $q(6)=3$: interval $I_3$ is the last one entirely left of
%          $I_6$.
\begin{tikzpicture}[
  >=Stealth,
  bar/.style={draw, fill=acc!15, minimum height=4.5mm, inner sep=2pt, font=\small},
  sel/.style={draw=acc, very thick, fill=acc!15, minimum height=4.5mm, inner sep=2pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % I_i = [start,finish] on x, stacked on y
  \node[bar, minimum width=14mm] (a) at (0.85,0)   {$I_1$};
  \node[bar, minimum width=15mm] (b) at (1.75,-0.7){$I_2$};
  \node[bar, minimum width=14mm] (c) at (2.65,-1.4){$I_3$};
  \node[bar, minimum width=16mm] (d) at (3.5,-2.1) {$I_4$};
  \node[bar, minimum width=15mm] (e) at (4.55,-2.8){$I_5$};
  \node[sel, minimum width=18mm] (f) at (4.65,-3.5){$I_6$};
  % time axis
  \draw[->, thick] (-0.4,-4.2) -- (6.6,-4.2) node[right, font=\footnotesize] {time};
  % left edge of I_6 (start), and the q(6)=3 pointer from I_3's finish
  \draw[dashed, acc] (3.75,-3.85) -- (3.75,0.35);
  \node[font=\footnotesize, acc] at (3.75,0.62) {start of $I_6$};
  \draw[->, very thick, red!75!black] (2.5,-1.62) .. controls (2.4,-2.5) and (2.9,-3.2) .. (3.72,-3.5);
  \node[font=\footnotesize, red!75!black, align=center] at (0.55,-2.7) {$q(6)=3$\\(last bar\\left of $I_6$)};
\end{tikzpicture}
$$

**Step 3: DP equations.** Consider the last interval $I_i$ and make one binary
choice — **include it or not**:
$$
\textsc{Opt}(i) =
\begin{cases}
0 & \text{if } i = 0, \\[4pt]
\max
\begin{cases}
\textsc{Opt}(i-1) & \text{// without } I_i \\[2pt]
p_i + \textsc{Opt}(q(i)) & \text{// with } I_i
\end{cases}
& \text{if } i \ge 1.
\end{cases}
$$
If we _exclude_ $I_i$, the best we can do is $\textsc{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 $\langle I_1, \dots, I_{q(i)}\rangle$, so we
add $\textsc{Opt}(q(i))$ — optimal substructure in action.

**Step 4: Correctness.**

> **Claim.** $\textsc{Opt}(i)$ equals the maximum profit obtainable from
> $\langle I_1, \dots, I_i\rangle$ for every $i \ge 0$.

> **Proof.** By induction on $i$. The base case $\textsc{Opt}(0) = 0$ is
> immediate: with no intervals the only feasible schedule is empty. For the step,
> any optimal schedule on the first $i$ intervals either omits $I_i$ — then it is
> an optimal schedule on the first $i-1$, worth $\textsc{Opt}(i-1)$ by the
> inductive hypothesis — or contains $I_i$ — then the rest is an optimal schedule
> on $\langle I_1,\dots,I_{q(i)}\rangle$ (the intervals compatible with $I_i$),
> contributing $p_i + \textsc{Opt}(q(i))$. Taking the max of the two cases
> reproduces the equation. $\qed$

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

```algorithm
caption: $\textsc{Iter-IS}(I_1, \dots, I_n)$ — max-profit interval scheduling
number: 4
sort intervals by increasing finish time $f_i$ // $O(n \log n)$
$\textsc{Opt}[0] \gets 0$
for $i \gets 1$ to $n$ do
  $k \gets q(i)$
  $\textsc{Opt}[i] \gets \max\parens{\textsc{Opt}[i-1],\ p_i + \textsc{Opt}[k]}$ // $O(1)$ per iteration
return $\textsc{Opt}[n]$
```

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

```algorithm
caption: $\textsc{Iter-IS}^{\prime}(I_1, \dots, I_n)$ — also reconstruct the set
number: 5
sort intervals by increasing finish time $f_i$
$\textsc{Opt}[0] \gets 0$
allocate boolean array $\textit{chosen}[1..n]$
for $i \gets 1$ to $n$ do
  $k \gets q(i)$
  if $\textsc{Opt}[i-1] \ge p_i + \textsc{Opt}[k]$ then
    $\textit{chosen}[i] \gets \text{false}$
    $\textsc{Opt}[i] \gets \textsc{Opt}[i-1]$
  else
    $\textit{chosen}[i] \gets \text{true}$
    $\textsc{Opt}[i] \gets p_i + \textsc{Opt}[k]$
return $\textsc{Opt}[n],\ \textit{chosen}$
```

Trace back from $i = n$: if $\textit{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 $\textsc{Opt}[i-1]$ and $\textsc{Opt}[q(i)]$,
takes the larger of the exclude value and $p_i$ plus the include value, and stores it
in $\textsc{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 $\textsc{Opt}[i]$ holds the true optimum, and
$\textsc{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
$$
O(n \log n).
$$

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

$$
% caption: Dependency graph of interval-scheduling subproblems sharing overlapping
%          entries.
\begin{tikzpicture}[
  >=Stealth,
  node distance=14mm,
  every node/.style={draw, circle, minimum size=8mm, inner sep=1pt, font=\small},
  every edge/.style={draw, ->, bend left=18}]
  \node (o5) {$5$};
  \node (o4) [below left=10mm and 6mm of o5] {$4$};
  \node (o3) [below=of o4] {$3$};
  \node (o2) [right=of o3] {$2$};
  \node (o1) [below right=10mm and 6mm of o3] {$1$};
  \node (o0) [right=14mm of o1] {$0$};
  \path (o5) edge (o4)        % Opt(5) -> Opt(4) = Opt(i-1)
        (o5) edge (o2)        % Opt(5) -> Opt(q(5)) = Opt(2)
        (o4) edge (o3)        % Opt(4) -> Opt(3)
        (o4) edge (o1)        % Opt(4) -> Opt(q(4)) = Opt(1)
        (o3) edge (o2)        % Opt(3) -> Opt(2)
        (o3) edge (o0)        % Opt(3) -> Opt(q(3)) = Opt(0)
        (o2) edge (o1)        % Opt(2) -> Opt(1)
        (o1) edge (o0);       % Opt(1) -> Opt(0)
\end{tikzpicture}
$$

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

::impl{algo="weighted_interval_scheduling"}

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

| length $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| price $p_i$ | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |

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
$\textsc{Opt}(i)$ be the max revenue from a rod of length $i$; we want
$\textsc{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:
$$
\textsc{Opt}(i) =
\begin{cases}
0 & \text{if } i = 0, \\[2pt]
\max\limits_{1 \le j \le i}\parens{p_j + \textsc{Opt}(i-j)} & \text{if } i \ge 1.
\end{cases}
$$
The subproblems $\textsc{Opt}(0), \dots, \textsc{Opt}(n)$ are ordered by length, so
we fill them in increasing order.

```algorithm
caption: $\textsc{Cut-Rod}(p[1..n])$ — maximum revenue cutting a length-$n$ rod
number: 6
$\textsc{Opt}[0..n] \gets 0$
for $i \gets 1$ to $n$ do
  for $j \gets 1$ to $i$ do
    $\textsc{Opt}[i] \gets \max\parens{\textsc{Opt}[i],\ p[j] + \textsc{Opt}[i-j]}$ // rightmost piece length $j$
return $\textsc{Opt}[n]$
```

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

| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| $\textsc{Opt}[i]$ | 0 | 1 | 5 | 8 | 10 | 13 | 17 | 18 | 22 |
| $\textit{rightmost}[i]$ | — | 1 | 2 | 3 | 2 | 2 | 6 | 1 | 2 |

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

$$
\textsc{Opt}[4] = \max
\begin{cases}
p_1 + \textsc{Opt}[3] = 1 + 8 = 9, \\
p_2 + \textsc{Opt}[2] = 5 + 5 = 10, \\
p_3 + \textsc{Opt}[1] = 8 + 1 = 9, \\
p_4 + \textsc{Opt}[0] = 9 + 0 = 9,
\end{cases}
= 10,
$$

won by $j = 2$, so $\textit{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 — $\textsc{Opt}[3], \textsc{Opt}[2], \textsc{Opt}[1], \textsc{Opt}[0]$
each feed several later rows, which is the overlap that makes the table pay off.

$$
% caption: Bottom-up fill of the rod-cutting table for the sample prices. Row Opt[i] is the
%          best revenue for length i; the arrow into Opt[4] shows its winning candidate
%          p_2 + Opt[2] = 10.
\begin{tikzpicture}[
  >=Stealth,
  clab/.style={draw=none, font=\footnotesize},
  cll/.style={draw, minimum size=8.5mm, inner sep=1pt, font=\small},
  won/.style={draw=acc, very thick, fill=acc!12, minimum size=8.5mm, inner sep=1pt, font=\small},
  src/.style={draw, fill=acc!8, minimum size=8.5mm, inner sep=1pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[clab] at (-1.5,0.72) {length $i$};
  \node[clab] at (-1.5,0)    {$\textsc{Opt}[i]$};
  \foreach \i in {0,...,8} { \node[clab] at (\i,0.72) {$\i$}; }
  \foreach \v/\x in {0/0,1/1,8/3,13/5,17/6,18/7,22/8} { \node[cll] at (\x,0) {$\v$}; }
  \node[src] (s2) at (2,0) {$5$};
  \node[won] (w4) at (4,0) {$10$};
  \draw[->, thick, acc] (s2) to[bend left=45] (w4);
  \node[clab, acc] at (3,1.15) {$p_2 + \textsc{Opt}[2] = 10$};
\end{tikzpicture}
$$

**Running time.** There are $n$ subproblems, and the work to compute
$\textsc{Opt}[i]$ is at most $b\,i$ for a constant $b$ (the inner loop runs $i$
times). Summing,
$$
T(n) = O(n) + \sum_{i=1}^{n} b\,i = O(n) + b\cdot\frac{n(n+1)}{2} = O(n^2),
$$
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 $\textit{rightmost}[i]$, then read them off by following
$n \to n - \textit{rightmost}[n] \to \cdots \to 0$.

```algorithm
caption: $\textsc{Print-Cut-Rod}(p[1..n])$ — print an optimal set of cuts
number: 7
$\textit{opt}, \textit{rightmost} \gets \textsc{Cut-Rod}^{\prime}(p)$ // also returns cut lengths
while $n > 0$ do
  print $\textit{rightmost}[n]$
  $n \gets n - \textit{rightmost}[n]$
```

::impl{algo="rod_cutting"}

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.

$$
% caption: Rod-cutting dependency DAG for n=5. Opt(i) depends on every Opt(k) with k < i;
%          the shared low-index nodes are the overlapping subproblems the table solves once.
\begin{tikzpicture}[
  >=Stealth,
  every node/.style={draw, circle, minimum size=8mm, inner sep=1pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {0,...,5} { \node (n\i) at (\i*1.6,0) {$\i$}; }
  % Opt(i) -> Opt(i-1) along the baseline
  \foreach \a/\b in {5/4,4/3,3/2,2/1,1/0} { \draw[->, acc] (n\a) -- (n\b); }
  % longer-range dependencies arc above
  \draw[->, acc, bend right=32] (n5) to (n3);
  \draw[->, acc, bend right=40] (n5) to (n2);
  \draw[->, acc, bend right=46] (n5) to (n1);
  \draw[->, acc, bend right=50] (n5) to (n0);
  \draw[->, black, bend left=32]  (n4) to (n2);
  \draw[->, black, bend left=40]  (n4) to (n1);
  \draw[->, black, bend left=46]  (n4) to (n0);
  \draw[->, black, bend right=32] (n3) to (n1);
  \draw[->, black, bend right=40] (n3) to (n0);
  \draw[->, black, bend left=32]  (n2) to (n0);
\end{tikzpicture}
$$

## 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 $\textit{chosen}$ and $\textit{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.[^bellman]

That decision-process lineage leads directly to
**reinforcement learning**. The Bellman equation $V(s) = \max_a \big(r(s,a) +
\gamma \sum_{s'} p(s'\mid s,a)\, V(s')\big)$ 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-\varepsilon})$
time unless the Strong Exponential Time Hypothesis fails — so the $\Theta(mn)$ table
of the [next lesson](/algorithms/dynamic-programming/sequence-dp) 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)$.

[^erickson-dp]: **Erickson**, Ch. 3 — Dynamic Programming: the working definition of dynamic programming as "recursion without repetition."
[^skiena-dp]: **Skiena**, §10 — Dynamic Programming: top-down memoization as caching results inside the natural recursion.
[^clrs-dp]: **CLRS**, Ch. 15 — Dynamic Programming: the optimal-substructure cut-and-paste test for a correct recurrence.
[^bellman]: **Bellman**, _Dynamic Programming_ (1957): the principle of optimality and the origin of the term. **Backurs & Indyk** (2015, STOC): edit distance has no strongly subquadratic algorithm unless SETH fails, a conditional lower bound matching the $\Theta(mn)$ table.