Introduction to Dynamic Programming
Imagine planning the cheapest way to type a document. You may insert, delete, or substitute characters. Each operation has a cost. A naive recursive solution recomputes the cost of aligning the same pairs of prefixes millions of times. The runtime explodes exponentially even for short strings. Yet almost all of that recomputation is wasted. The same small set of subproblems keeps reappearing. Dynamic programming (DP) is the design paradigm that recognizes this redundancy and eliminates it. It turns exponential-time brute force into polynomial-time computation. This works by solving each distinct subproblem exactly once and reusing the answer. DP sits at the center of algorithmic practice. So many real optimization problems decompose into overlapping smaller instances of themselves. Examples include sequence alignment in bioinformatics, shortest paths in routing, resource allocation, speech recognition decoding, and compiler register allocation. Whenever a problem can be described by a recurrence relating the answer for a large input to answers for smaller inputs, DP becomes useful. This applies whenever those smaller inputs recur across different branches of the recursion. DP is the tool that makes the computation tractable. It is the disciplined generalization of an idea every programmer eventually reinvents: cache the answer instead of recomputing it. This article builds on The Divide and Conquer Paradigm, which also decomposes problems into subproblems. It also builds on The Greedy Method and Optimal Substructure, which exploits optimal substructure without worrying about overlap. DP keeps the optimal-substructure requirement from greedy algorithms. But it drops the assumption that a single locally-optimal choice suffices. Instead it examines all choices and lets the recurrence — a Bellman equation — combine them correctly. The result is a systematic way to convert an exponential search tree into a polynomial-size table. By the end of this article you will be able to recognize when a problem exhibits overlapping subproblems and optimal substructure. You will be able to write down a Bellman recurrence precisely. You will also turn that recurrence into a working algorithm using either top-down memoization or bottom-up tabulation. You will understand exactly why the technique is correct, via an induction on subproblem size. You will also understand why it is efficient, via a counting argument on distinct subproblems. Later articles specialize this machinery to The 0/1 Knapsack Problem and Longest Common Subsequence, among many others.
- Dynamic programming solves problems with optimal substructure and overlapping subproblems by computing each distinct subproblem once and storing its answer.
- The core object is a Bellman recurrence: the optimal value of a problem expressed in terms of optimal values of smaller subproblems.
- Two equivalent implementation strategies exist: top-down memoization (recursion + cache) and bottom-up tabulation (iterative table filling in dependency order).
- Correctness follows by strong induction on subproblem size, given that the recurrence itself is proven correct via an exchange/optimality argument.
- Efficiency follows by bounding the number of distinct subproblems and the work per subproblem, giving total time = (#subproblems) × (time per subproblem).
- DP generalizes The Greedy Method and Optimal Substructure by exploring all choices instead of committing to one, at the cost of needing memory to avoid recomputation.
Dynamic programming trades memory for time by solving each overlapping subproblem exactly once, using a provably correct recurrence over optimal substructure.
The idea
A problem exhibits optimal substructure if an optimal solution to it can be constructed from optimal solutions to smaller subproblems of the same type. This is the same property that makes greedy algorithms and divide-and-conquer work. What distinguishes dynamic programming is the second property: overlapping subproblems. In divide-and-conquer, the subproblems generated by recursion are typically disjoint (e.g., the two halves of an array in mergesort never share elements), so a plain recursive algorithm is already efficient. In DP, the recursion tree instead revisits the same subproblem along exponentially many different root-to-leaf paths — for example, computing the edit distance between prefixes of length `i` and `j` is needed by the computations for `(i+1, j)`, `(i, j+1)`, and `(i+1, j+1)` alike. The formal object that captures optimal substructure is a Bellman recurrence (named for Richard Bellman, who coined "dynamic programming" in the 1950s): an equation expressing the optimal value `V(x)` of an instance `x` in terms of the optimal values `V(x₁), V(x₂), …` of strictly smaller instances, together with a base case for the smallest instances. Schematically, ``` V(x) = base_value if x is a base case V(x) = opt over choices c of { cost(c) + V(next(x, c)) } otherwise ``` where `opt` is `min` or `max` depending on whether we are minimizing cost or maximizing value, and `next(x, c)` maps an instance and a choice to a strictly smaller instance. A recurrence like this is not automatically true — it must be proven, typically by an exchange argument showing that any optimal solution to `x` must, when restricted appropriately, be an optimal solution to one of the `next(x, c)`. Once a correct Bellman recurrence is in hand, DP is the technique of evaluating it efficiently by recognizing that the set of distinct instances `x` that ever appear is small (polynomial in the input size, not exponential), and storing `V(x)` for each such instance the first time it is computed. Two standard implementation strategies realize this idea:
- Top-down memoization: write the recurrence as ordinary recursion, but before recursing, check a cache (memo table) keyed by the subproblem; if present, return the cached value; otherwise compute it, store it, and return it.
- Bottom-up tabulation: identify a linear order on subproblems consistent with the dependency structure (smaller subproblems first), and fill a table iteratively, so that every value needed by the recurrence for `x` has already been computed by the time `x` is processed.
These two strategies always compute the same values; the choice between them is an implementation detail (explored further in Memoization versus Tabulation), not a difference in what is being computed.
How it works
We walk through the general mechanism using edit distance (Levenshtein distance) as the running example: given strings `A[1..m]` and `B[1..n]`, find the minimum number of single-character insertions, deletions, and substitutions to transform `A` into `B`.
Step 1 — Define the subproblem parametrically. Choose a family of subproblems indexed by parameters that shrink as recursion proceeds. Here: `D(i, j)` = edit distance between `A[1..i]` and `B[1..j]`, for `0 ≤ i ≤ m`, `0 ≤ j ≤ n`.
Step 2 — State the recurrence (Bellman equation) and prove it. Consider an optimal alignment of `A[1..i]` and `B[1..j]`. Look at the last operation applied to align the final characters:
- Delete `A[i]` (align it to nothing): cost `1 + D(i-1, j)`.
- Insert `B[j]` (align nothing to it): cost `1 + D(i, j-1)`.
- Match/substitute `A[i]` with `B[j]`: cost `[A[i] ≠ B[j]] + D(i-1, j-1)`.
Any optimal solution must end in one of these three ways, and whichever way it ends, the remaining prefix alignment must itself be optimal — otherwise we could splice in a cheaper prefix alignment and strictly improve the whole solution, a contradiction. This exchange argument is exactly what optimal substructure requires, and it yields: ``` D(i, 0) = i (delete all of A[1..i]) D(0, j) = j (insert all of B[1..j]) D(i, j) = min( 1 + D(i-1, j), 1 + D(i, j-1), [A[i] ≠ B[j]] + D(i-1, j-1) ) for i, j ≥ 1 ```
Step 3 — Identify the subproblem space and dependency order. There are `(m+1)(n+1)` distinct pairs `(i, j)`, and `D(i, j)` depends only on `D(i-1, j)`, `D(i, j-1)`, `D(i-1, j-1)` — all with strictly smaller `i + j`. So any order that processes `(i, j)` after all pairs with smaller `i` and smaller `j` (e.g., row-major order) is valid.
Step 4 — Implement via tabulation or memoization. ``` function EDIT-DISTANCE(A[1..m], B[1..n]): let D[0..m][0..n] be a new table for i = 0 to m: D[i][0] = i // base case: delete all of A[1..i] for j = 0 to n: D[0][j] = j // base case: insert all of B[1..j] for i = 1 to m: for j = 1 to n: substCost = (A[i] == B[j]) ? 0 : 1 D[i][j] = min( D[i-1][j] + 1, // delete A[i] D[i][j-1] + 1, // insert B[j] D[i-1][j-1] + substCost // match or substitute ) return D[m][n] ``` The equivalent memoized top-down version makes the "compute once" behavior explicit with a cache: ``` memo = empty map // keys: (i, j) pairs function EDIT-DISTANCE-MEMO(A, B, i, j): if (i, j) in memo: return memo[(i, j)] if i == 0: result = j else if j == 0: result = i else: substCost = (A[i] == B[j]) ? 0 : 1 result = min( EDIT-DISTANCE-MEMO(A, B, i-1, j) + 1, EDIT-DISTANCE-MEMO(A, B, i, j-1) + 1, EDIT-DISTANCE-MEMO(A, B, i-1, j-1) + substCost ) memo[(i, j)] = result return result ```
Step 5 (optional) — Reconstruct the solution. If the actual sequence of edits is needed, not just its cost, store at each cell a pointer to which of the three cases achieved the minimum, then walk the pointers back from `D[m][n]` to `D[0][0]`. The figure below shows the dependency structure of the table: each cell depends only on the cell above, the cell to the left, and the cell diagonally above-left, which is exactly why a row-major fill order is safe and why the DAG of subproblems has no cycles.
Complexity & correctness
Time complexity. The number of distinct subproblems is `(m+1)(n+1) = Θ(mn)`. Each subproblem does `O(1)` work (a fixed number of comparisons and additions among already-computed values). By the fundamental DP counting principle, ``` total time = (number of distinct subproblems) × (time to combine per subproblem) = Θ(mn) × Θ(1) = Θ(mn) ``` This is a dramatic improvement over the naive recursive algorithm without memoization, whose recursion tree has depth `Θ(m+n)` and branches up to 3-way at every level, giving `Ω(3^{min(m,n)})` calls in the worst case — genuinely exponential. Memoization or tabulation collapses this tree into a DAG with only `Θ(mn)` distinct nodes, and the exponential blow-up disappears entirely because every node is visited once instead of once per path reaching it.
Space complexity. The table itself is `Θ(mn)`. If only the optimal value (not the edit sequence) is needed, space can be reduced to `Θ(min(m,n))` by observing that row `i` of the table depends only on row `i-1`, so only two rows need to be kept in memory at a time (a common DP space-optimization). Reconstructing the actual sequence of edits, however, generally requires the full table or a more involved technique such as Hirschberg's algorithm, which recovers `O(m+n)` space using divide-and-conquer on top of DP.
Correctness — proof sketch by strong induction on `i + j`. We show `D(i, j)` as computed by the algorithm equals the true edit distance, by strong induction on `s = i + j`. Base case (`s = 0`, i.e., `i = j = 0`): `D(0,0) = 0`, correctly the cost of aligning two empty strings. More generally the base row/column `D(i,0) = i` and `D(0,j) = j` are correct because the only alignment of a string against the empty string is to delete/insert every character. Inductive step: assume `D(i', j')` is correctly computed for all `i' + j' < s`. For `(i,j)` with `i+j=s` and `i,j ≥ 1`, the earlier exchange argument shows that any optimal alignment of `A[1..i]`, `B[1..j]` ends in a deletion, insertion, or match/substitution, and in each case the remaining alignment restricted to the smaller prefixes must itself be optimal (otherwise splice in a strictly better sub-alignment, contradicting optimality of the whole). Hence the true distance equals the minimum of the three candidate expressions, each of which references only subproblems of index sum `< s`, which are correct by the inductive hypothesis. Since the algorithm computes exactly this minimum, `D(i,j)` is correct. By induction, `D(i,j)` is correct for all `(i,j)`, in particular `D(m,n)`. ∎ This two-part structure — (1) prove the recurrence itself correct via an exchange/optimality argument, (2) prove the algorithm computes the recurrence correctly via induction on subproblem size — is the general template for verifying any DP algorithm, not just this one.
Honest tradeoffs. DP requires that the number of distinct subproblems be polynomial; if the natural parameterization has exponentially many reachable states (e.g., subsets of a large set, as in the traveling salesman DP over `2^n` subsets), DP is still exponential, just less so than brute force. DP also assumes the recurrence's "smaller subproblem" relation is acyclic — if a problem's optimal substructure is circular (as with some shortest-path problems containing negative cycles), naive DP recurrences fail and specialized algorithms (Bellman–Ford's relaxation-based approach, which tolerates a bounded number of relaxation rounds) are needed instead. Finally, memoization can incur overhead from hashing/dictionary lookups that pure array-indexed tabulation avoids, which matters in performance-critical code.
Worked example
Trace `EDIT-DISTANCE` on `A = "SATURDAY"` restricted to a short slice for clarity — take `A = "SUNDAY"`, `B = "SATURDAY"` is longer, so instead trace the compact classic pair `A = "GATC"`, `B = "GACT"` (`m = n = 4`), useful in bioinformatics-style alignment. Substitution, insertion, deletion each cost 1. Fill the table row by row (rows indexed by `i` over `A = G A T C`, columns by `j` over `B = G A C T`):
| D | "" | G | A | C | T |
|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 |
| G | 1 | 0 | 1 | 2 | 3 |
| A | 2 | 1 | 0 | 1 | 2 |
| T | 3 | 2 | 1 | 1 | 1 |
| C | 4 | 3 | 2 | 1 | 2 |
Key cells traced explicitly:
- `D[1][1]` (`A` prefix `"G"`, `B` prefix `"G"`): `A[1]=G = B[1]=G`, so substCost = 0. `min(D[0][1]+1=2, D[1][0]+1=2, D[0][0]+0=0) = 0`. Matches — no edit needed yet.
- `D[3][3]` (`"GAT"` vs `"GAC"`): `A[3]=T ≠ B[3]=C`, substCost = 1. `min(D[2][3]+1 = 1+1=2, D[3][2]+1 = 1+1=2, D[2][2]+1 = 0+1=1)`. Minimum is 1, achieved via the diagonal (substitute T→C after having aligned `"GA"` to `"GA"` for free).
- `D[4][4]` (full strings `"GATC"` vs `"GACT"`): `A[4]=C ≠ B[4]=T`, substCost = 1. `min(D[3][4]+1 = 1+1=2, D[4][3]+1 = 1+1=2, D[3][3]+1 = 1+1=2)`. All three tie at 2, so `D[4][4] = 2`.
Answer: the edit distance between `"GATC"` and `"GACT"` is 2 — e.g., substitute the `T` at position 3 with `C`, and substitute the `C` at position 4 with `T` (equivalently, this is a transposition realized as two substitutions, since plain edit distance has no transposition operation). Tracing back-pointers from `D[4][4]` through the diagonal at each tie confirms one such optimal alignment. Contrast with the naive exponential recursion: without memoization, computing `D(4,4)` this way re-derives `D(2,2)` through many different call paths — it is called once directly from `D(3,3)`'s diagonal branch, but also indirectly from `D(3,2)` and `D(2,3)`'s branches, and so on — a redundancy that would grow as `Θ(3^{4})` calls in the worst case for strings of length 4, versus the `Θ(16)` table cells actually filled by the DP algorithm.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Wrong base case | Off-by-one on empty prefixes (e.g., `D[0][0]` undefined or `D[i][0]` computed as `0` instead of `i`) | Explicitly derive base cases from the problem's degenerate instance (empty string, empty set, zero capacity) before coding |
| Filling table in wrong order | Assuming row-major order works for every recurrence without checking the dependency direction | Draw the dependency arrows (as in the figure) and confirm every cell's dependencies are filled first |
| Confusing "a" greedy choice with optimal substructure | Believing one locally-best choice at each step suffices, as in greedy algorithms | Verify overlapping/non-monotone tradeoffs exist; if a single greedy criterion is provably optimal, DP is unnecessary overhead |
| Exponential blow-up from missing memoization | Writing the correct recurrence but implementing it as plain recursion with no cache | Add a memo table keyed by the exact subproblem parameters, and check it before recursing |
| Recomputing state not actually needed | Treating extra parameters (indices) as part of the state when a smaller parameterization suffices, ballooning subproblem count | Minimize the state: only include parameters the recurrence actually depends on |
| Off-by-one in reconstructing the solution | Backtracking pointers misaligned with 0- vs 1-indexed arrays | Keep index conventions for the DP table and the original arrays consistent throughout, and test on the smallest nontrivial instance |
Pioneers & history
Origins · 1 minRichard E. Bellman and how this was discovered
Bellman developed dynamic programming in the early 1950s while working at the RAND Corporation on multistage decision processes in control theory and operations research. He coined the term "dynamic programming" partly because "programming" then meant tabular planning (as in military logistics), and partly, by his own account, to make the work sound appealing to a funding agency skeptical of mathematical research — "dynamic" could not possibly have a bad connotation. His principle of optimality, stating that an optimal policy has the property that whatever the initial decision, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision, is the mathematical core of what this article calls optimal substructure and the Bellman recurrence.
Where this matters
Dynamic programming underlies technologies far beyond textbook exercises. The Unix `diff` utility and version-control systems (Git) compute minimal edit scripts between file revisions using edit-distance-style DP. Bioinformatics tools for DNA and protein sequence alignment (BLAST's seed-and-extend heuristics build on exact DP aligners like Needleman–Wunsch and Smith–Waterman) rely on exactly the recurrence developed above. Speech recognition and natural-language processing systems historically used the Viterbi algorithm, a DP over hidden Markov model states, to decode the most likely sequence of phonemes or tags. Compilers use DP for optimal instruction selection and register allocation on expression trees. Network routing protocols compute shortest paths using DP-based relaxation (Bellman–Ford), especially where negative-weight edges or distributed computation make Dijkstra's greedy approach unsuitable. In reinforcement learning and control theory, value iteration and policy iteration are direct applications of the Bellman equation to Markov decision processes, and the same principle-of-optimality reasoning justifies both. Financial applications include optimal portfolio rebalancing and option pricing via binomial trees, both DP recurrences over time steps. Anywhere a problem can be phrased as a sequence of decisions with a recursively decomposable cost and a manageable state space, dynamic programming is the default design paradigm to reach for.
Ask the tutor: How do I decide what the "state" of a subproblem should be when a problem has many possible parameters to track?
What is the difference between optimal substructure and overlapping subproblems?
Optimal substructure means an optimal solution to a problem can be built from optimal solutions to smaller instances of the same problem — this property alone is shared with greedy algorithms and divide-and-conquer. Overlapping subproblems means that, when this decomposition is applied recursively, the same smaller instance is generated repeatedly along different branches of the recursion tree, rather than each subproblem appearing only once. Dynamic programming specifically exploits both together: it needs optimal substructure to write a correct recurrence, and it needs overlap to make caching worthwhile — without overlap, a plain recursive divide-and-conquer algorithm would already be efficient, since there would be nothing to save by memoizing.
Is dynamic programming always polynomial time?
No. Dynamic programming is only as fast as (number of distinct subproblems) × (time per subproblem). If the natural state space is exponential in the input size — for example, DP over all `2^n` subsets of a set, as in the Held–Karp algorithm for the traveling salesman problem — the resulting algorithm is still exponential, just asymptotically better than brute-force enumeration of all orderings. DP is a technique for eliminating redundant recomputation of subproblems that recur; it does not shrink the subproblem space itself. Whether DP yields a polynomial algorithm depends entirely on whether the chosen state parameterization has polynomially many reachable values.
How do I know if a problem is a good candidate for dynamic programming?
Look for two signatures. First, can you write a recurrence expressing the answer to an instance in terms of answers to strictly smaller instances (optimal substructure)? Try an exchange argument: assume an optimal solution, look at its last decision, and check whether the rest of the solution must be optimal for a smaller instance. Second, does a direct recursive implementation of that recurrence call the same smaller instance many times? If you can name the subproblem with a small tuple of parameters (like `(i, j)` for two string indices) and that tuple space is polynomial in the input size, DP applies directly. If either property fails, consider The Divide and Conquer Paradigm (no overlap) or The Greedy Method and Optimal Substructure (a single locally optimal choice suffices).
What is a Bellman recurrence, precisely?
A Bellman recurrence is an equation of the form `V(x) = base` for base-case instances `x`, and `V(x) = opt_{c ∈ choices(x)} [ cost(c) + V(next(x,c)) ]` otherwise, where `opt` is `min` or `max`, `choices(x)` enumerates the decisions available at instance `x`, and `next(x,c)` maps a choice to a strictly smaller subproblem. It formalizes Bellman's principle of optimality: whatever the first decision, the remaining decisions must be optimal for the resulting smaller state. Writing this equation down precisely — including correct base cases and a proof that it captures every possible optimal solution — is the mathematical heart of designing any DP algorithm; the implementation (memoization or tabulation) is comparatively mechanical once the recurrence is verified correct.
Why does the article emphasize proving the recurrence, not just coding it?
Because a plausible-looking recurrence can be subtly wrong, and no amount of correct implementation will fix a wrong recurrence. The proof step — typically an exchange or cut-and-paste argument showing that any optimal solution restricted to a smaller instance must itself be optimal for that instance — is what guarantees the recurrence actually characterizes optimal values, rather than merely some heuristic combination of subproblem answers. Skipping this step is a common source of DP bugs that are invisible on small test cases: the code runs and returns a number, but the recurrence silently fails to consider some class of optimal solutions, and the answer is wrong only on inputs where that class matters.
How does dynamic programming relate to memoization versus tabulation?
Memoization and tabulation are two implementation strategies for evaluating the same underlying Bellman recurrence; they always compute identical values. Memoization is top-down: write ordinary recursion following the recurrence, and cache each result the first time it is computed, checking the cache before recursing further. Tabulation is bottom-up: determine an order on subproblems consistent with dependencies (smaller subproblems first) and fill a table iteratively. Memoization can be simpler to derive directly from the recurrence and only computes subproblems actually needed, while tabulation avoids recursion overhead and often enables space optimizations like keeping only the last one or two rows of a table. The deeper comparison, including when each is preferable, is developed in Memoization versus Tabulation.
Does dynamic programming ever fail even when optimal substructure holds?
Yes, in two main ways. First, if the "smaller instance" relation is not actually acyclic — for instance, some naive shortest-path recurrences over graphs with negative cycles — the recursion never bottoms out, and specialized algorithms with bounded iteration counts (like Bellman–Ford, which performs at most `V-1` relaxation rounds and detects negative cycles explicitly) are needed instead of plain DP. Second, if the natural state space is exponential, DP degrades to an exponential algorithm, merely faster than brute force by a polynomial-versus-exponential-in-a-different-base factor; problems like the general traveling salesman problem fall here, where DP achieves `O(n^2 2^n)` rather than `O(n!)`, an improvement but still intractable for large `n`.