Algorithmic Patterns

Dynamic programming

Overlapping subproblems and optimal substructure

~14 minLesson 15 of 25Written by Claude Opus 4.8

Some problems break into smaller copies of themselves - and those copies keep reappearing. Naive recursion re-solves each one from scratch, and the repeated work explodes exponentially. Dynamic programming (DP) fixes this with one embarrassingly simple idea: solve each distinct subproblem exactly once, store its answer, and look it up ever after. Trading a little memory for a lot of recomputation collapses exponential algorithms into polynomial ones. We will watch it happen on edit distance - the algorithm that measures how many single-character edits separate two words.

The one-line idea

If the same subproblem is needed over and over, do not recompute it - remember it. A recursion tree with billions of nodes but only a few thousand distinct questions is really a small table wearing a big costume. DP is just that table, filled in a sensible order.

Two conditions that make DP work

DP is not magic and it does not apply everywhere. A problem is a DP problem when it has two properties at once:

1. Overlapping subproblems. The naive recursion asks the same question many times. For edit distance, edit(i, j) - the cost to align the first $i$ letters of one word with the first $j$ of another - branches into edit(i-1, j), edit(i, j-1), and edit(i-1, j-1). Those branches fan out exponentially, yet they collide constantly: there are only $(m + 1) (n + 1)$ distinct $(i, j)$ pairs. Everything past that first visit is wasted work.

2. Optimal substructure. An optimal answer to the whole problem is built from optimal answers to its subproblems. If you know the best way to edit the shorter prefixes, one more comparison extends it to the best way to edit the longer ones. That is exactly the "take the minimum of three options" step you are about to see - and it is what makes storing subresults safe.

Without overlap, DP buys you nothing

Merge sort's subproblems never repeat - each half is unique - so there is nothing to cache, and a plain divide-and-conquer is already optimal. DP earns its keep only when subproblems overlap. That is the single question to ask before reaching for a table: "am I about to recompute something I have already solved?"

State and transition: the edit-distance recurrence

Every DP is two decisions. First, define the state - the smallest set of facts that names a subproblem. For edit distance between word $a$ (length $m$ ) and word $b$ (length $n$ ), the state is a pair $(i, j)$ , and

D [i] [j] = the minimum edits to turn the first i letters of a into the first j letters of b .

Second, define the transition - how a state's answer is assembled from smaller states. To match one more letter you either delete from $a$ (step down a row), insert into $a$ (step right a column), or substitute along the diagonal - free if the two letters already match. Take the cheapest:

D [i] [j] = min ⎩ ⎨ ⎧ D [i - 1] [j] + 1 D [i] [j - 1] + 1 D [i - 1] [j - 1] + 1 [a_{i} \neq = b_{j}] delete a_{i} insert b_{j} substitute / match

The base cases anchor the recursion. Turning any prefix into the empty string $ε$ is all deletions; building any prefix from $ε$ is all insertions:

D [i] [0] = i, D [0] [j] = j .

The indicator $1 [a_{i} \neq = b_{j}]$ is $1$ when the letters differ (a real substitution) and $0$ when they already match (the diagonal is free). Fill the grid so that every cell's three neighbours are ready before it, and the bottom-right corner is the answer.

Fill the table, then trace back

Here is the recurrence made physical. We turn cat into cute. Step through the interior cell by cell: each cell reaches up (delete), left (insert), and diagonally (substitute/match), takes the smallest, and records it. When the grid is full, the corner holds the edit distance - and following each cell back to the neighbour it chose reconstructs the exact edits.

Edit-distance table filler step each cell - then trace back

match ↖ (free)substitute ↖delete ↑insert ←optimal path

Base cases first. The top row and left column are free - turning a prefix into ε is all deletes; building one from ε is all inserts.

Base cases fill the free row and column.

←top row D[0][j] = j - build "cute" from ε by inserting

↑left col D[i][0] = i - shrink "cat" to ε by deleting

Every interior cell = min(up, left, diagonal), +1 unless the letters match.

The rows are the letters of cat (plus the empty string ε on top); the columns are the letters of cute (plus ε on the left). Each interior cell is the min of its three filled neighbours.

The aha: the table is the recursion, memoized

Every arrow you stepped through is one line of the recurrence, evaluated once and written down. The naive recursion would have re-derived edit(1, 1) - the "match c" cell - from scratch for nearly every path through the tree. Here it is computed a single time and read four times during traceback. Same answer, but

O (3^{m + n})

recomputation becomes

O (mn)

lookups. The traceback is the payoff: the numbers alone tell you the distance is 2, but the arrows tell you which two edits - substitute a→u, then insert e. That reconstruction is what turns a cost into an actual answer.

Top-down vs bottom-up: two ways to fill the same table

There are exactly two ways to populate the DP table, and they compute identical values.

Top-down (memoization) keeps the natural recursion but adds a cache: before solving a state, check whether it is already stored; after solving, store it. You only ever touch the states you actually need, and the code reads like the recurrence.

Bottom-up (tabulation) throws away recursion entirely and fills the grid in dependency order with plain loops - smallest subproblems first - so every neighbour is ready when you reach a cell. No call stack, slightly faster in practice, and easy to shrink to $O (min (m, n))$ memory by keeping just one row. That is the version the demo animates:

def edit_distance(a, b):          # Levenshtein: fewest insert/delete/substitute
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1): dp[i][0] = i    # delete every letter of a
    for j in range(n + 1): dp[0][j] = j    # insert every letter of b

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,        # delete
                           dp[i][j - 1] + 1,        # insert
                           dp[i - 1][j - 1] + cost)   # substitute / match
    return dp[m][n]

edit_distance("cat", "cute")   # -> 2

Edit distance - bottom-up tabulation

Why it is fast, and where the memory goes

There are

(m + 1) (n + 1)

states, and each does

O (1)

work - one comparison and a three-way minimum - so the running time is

O (mn)

, down from the

O (3^{m + n})

of blind recursion. Space is

O (mn)

if you keep the whole grid, but a cell only ever reads the current and previous rows, so a rolling array shrinks it to

O (min (m, n))

. The catch: once you discard old rows you can no longer trace back, so keep the full grid whenever you need the actual edit script, not just its length.

Check yourself

Dynamic programming pays off precisely when a problem's subproblems are:

Each interior cell of the edit-distance table is filled by taking the minimum over:

Recall the edit-distance recurrence, its base cases, and its running time.

Recall the loop invariant. Try to state it, then check.

Lock it in

DP applies exactly when a problem has both overlapping subproblems and optimal substructure: solve each distinct subproblem once, store it, and look it up ever after.
Trading a little memory for a lot of recomputation collapses exponential recursion into polynomial time.
Edit distance fills an $(m + 1) (n + 1)$ table; each interior cell is the min of its up, left, and diagonal neighbours plus a step, so the whole thing is $O (mn)$ time and space.
A rolling row cuts space to $O (min (m, n))$ , but you forfeit the traceback that reconstructs the actual alignment.

Primary source

For a rigorous, worked lecture series that builds the DP mindset from scratch - recurrences, memoization, and tabulation - watch Abdul Bari's Dynamic Programming playlist. For deliberate, category-by-category practice, work the 1-D and 2-D DP sections of the NeetCode Roadmap - edit distance lives in the 2-D DP group alongside its close cousins (longest common subsequence, coin change, and the knapsack family).

Ask your teacher

This exact grid is why DP shows up all over language technology. Edit distance is the classic sequence-alignment table, and the same "fill a table of subproblem answers" pattern powers Viterbi decoding, which finds the most probable hidden sequence in a model. The deeper thread - reuse a stored subresult instead of recomputing it - is precisely the insight behind the KV cache that makes LLM generation fast: past keys and values are computed once and read on every new token, never redone. Ask me how traceback in this table mirrors the Viterbi backpointer, why the rolling-array trick forfeits reconstruction, or how the KV cache is "memoization for attention."