Dynamic Programming From Scratch — On Remembering Subproblems

Why naive recursion explodes exponentially, what memoization and table-filling actually change, and Fibonacci, knapsack and edit distance taken apart in order — ending at the places edit distance shows up in real AI systems, from ASR word error rate to diffusion step schedules.

The metaphor: are you re-measuring the same trail?

You are on an unmapped mountain and want the fastest route to the summit. At every fork you work out "how many minutes to the top going left?" and "how many going right?", then take the shorter one. Reasonable — except mountain trails rejoin. The stretch above a junction gets measured once while you evaluate the left branch and again while you evaluate the right one. You are re-measuring identical terrain over and over.

Just write the answer in a notebook the first time. When you reach that junction again, read instead of measure. That is the entirety of dynamic programming (DP). The name is forbidding; the content is nothing more than remembering the answers to subproblems.

Why naive recursion explodes

Fibonacci makes it visible, because the definition is already a recursion.

Put in words: "the $n$-th value is the sum of the two before it." Nothing more is being claimed. $F$ is a function that hands you a value when you give it a position, $n$ is that position, and $F(0)=0,\ F(1)=1$ is the declaration that the first two are fixed by hand so the recursion has somewhere to stop. Transcribed literally, it is three lines.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

Correct, but fib(40) makes you wait and fib(60) never returns. Draw the call tree and the reason appears: computing fib(5) calls fib(3) twice, fib(2) three times, fib(1) five times. Each increment of $n$ multiplies the number of branches by the golden ratio $\varphi = (1+\sqrt{5})/2 \approx 1.618$, so the cost is $O(\varphi^n)$ — exponential, the "not a plan" row of the table in the complexity article.

The waste is precisely identifiable. Calls with identical arguments keep restarting from scratch.

Memoization: compute once, remember forever

Keep one dictionary and store answers as they are computed.

def fib(n, memo={}):
    if n < 2: return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Three added lines drop the cost from $O(\varphi^n)$ to $O(n)$. There are only $n+1$ subproblems, $F(0)$ through $F(n)$, and each body now runs exactly once; every later encounter is a dictionary lookup, $O(1)$ on average (data structures).

Exponential to linear. This is the most satisfying instance of buying time with memory there is. The style is called memoization, or top-down DP.

Filling the table: bottom-up DP

The same thing can be written without recursion at all — fill a table starting from the smallest subproblems.

def fib(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

The complexity matches memoization, but recursion depth stops being a concern and the constants are lighter. More importantly, the table makes waste visible. This recurrence only ever reads the previous two entries, so the array is unnecessary and two variables suffice — space falls from $O(n)$ to $O(1)$. Filling the table and then discarding the rows you never look at is standard practice.

The two conditions for DP

Not every problem yields to DP. Exactly two properties are required.

1. Optimal substructure — the optimal solution to the whole is assembled from optimal solutions to its parts
2. Overlapping subproblems — the same subproblem recurs many times

Without the first, DP returns a confidently wrong answer. Without the second, you have plain divide and conquer and remembering buys nothing.

And in practice, designing a DP is almost entirely deciding what counts as a subproblem. Once the state is defined, the recurrence writes itself.

Knapsack: take it or leave it

Fill a bag of capacity $W$ with items of weight $w_i$ and value $v_i$ to maximize total value. Brute force means $2^n$ subsets.

Define the subproblem as "the best value achievable considering only the first $i$ items, with capacity $w$", written $dp[i][w]$.

Put in words, $\max$ means "keep whichever of the two candidates is better" and $w - w_i$ means "set aside exactly this item's weight in the bag". The equation is saying that the whole decision reduces to one binary question: item $i$, in or out?

There are only two things to do with item $i$. Leave it and the value is whatever the first $i-1$ items achieved (left term). Take it and you get its value $v_i$ plus the best answer for a bag that had its weight reserved (right term). Keep the larger. That is the whole recurrence.

The table has $n \times W$ cells, so the cost is $O(nW)$ — an enormous improvement on $2^n$, with one caveat. $W$ is not a count of items; it is a number written in the input. A huge $W$ means a huge table. This is called pseudo-polynomial time, and it is worth remembering as the marker of where DP stops helping.

Edit distance: how much repair until two strings match?

Edit distance (Levenshtein distance) is the minimum number of edits that turn string $s$ into string $t$, where an edit substitutes, deletes or inserts one character.

The subproblem is "the fewest edits turning the first $i$ characters of $s$ into the first $j$ characters of $t$", written $D[i][j]$.

Put in words, each $+1$ is the price of spending one edit and $\min$ means "take the cheapest repair available" — which says: of the three states one step back, arrive here by whichever route costs the fewest edits.

Here $c$ is 0 if the $i$-th character of $s$ equals the $j$-th of $t$, and 1 otherwise. The three candidates are the three edits: the first deletes a character from $s$, the second inserts one from $t$, the third substitutes (moving diagonally at zero cost when the characters already agree). Take the smallest and you have the minimum up to that point.

def edit_distance(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i          # delete all of s
    for j in range(n + 1): dp[0][j] = j          # insert all of t
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            c = 0 if s[i - 1] == t[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,     # deletion
                           dp[i][j - 1] + 1,     # insertion
                           dp[i - 1][j - 1] + c) # substitution
    return dp[m][n]

The nested loops fill the table from top-left to bottom-right, and the bottom-right cell is the answer. Cost $O(mn)$; space is $O(mn)$ as written, but since each row only reads the row above it, keeping two rows brings that down to $O(n)$.

This exact table shows up inside AI systems

Edit distance is not a competitive-programming exercise. It is working equipment.

Word error rate in speech recognition. Transcription accuracy is scored as

$$\mathrm{WER} = \frac{S + D + I}{N}$$

which says: count the words you got wrong, divide by how many words the reference had. Zero means a perfect transcript, and the larger the number the more errors there were. Here $S$ is substitutions, $D$ deletions, $I$ insertions and $N$ the words in the reference. Those three counts are obtained by filling the edit-distance table with words as the atomic symbols and backtracing the optimal path. The definition of the metric is the recurrence above. ROUGE-L, used in summarization, rests on longest common subsequence — the same kind of DP.

Sequence alignment. Viterbi decoding in HMMs, the CTC forward pass, dynamic time warping for audio. Each stores "the best value for being in state $s$ at time $t$" in a table and transitions in from neighbouring cells: structurally identical to edit distance.

Choosing diffusion steps. When you want to cut the number of sampling steps, and the objective decomposes into a sum of per-step contributions, "which timesteps to keep" can be chosen optimally by DP rather than by search — methods of exactly this shape have been proposed. Notice that deciding keep-or-drop in sequence is the same structure as knapsack, and the tool is already in your hands.

Matrix chain order. Multiplying several matrices, the order of association changes the total operation count substantially. Finding the optimal parenthesization is a classic DP — which leads directly into the next article.

Four things that matter in practice

1. Write the naive recursion first Once the recursion is correct, memoization is one dictionary away. Designing the table directly usually produces a subtly wrong recurrence.

2. Write the meaning of the state in a sentence Put what $dp[i][j]$ denotes into a comment, in prose. Most DP bugs come from that definition drifting halfway through the implementation.

3. Fill the boundaries before the interior Edge rows and columns like $D[i][0]$ and $D[0][j]$ come from the meaning of the problem, not from the recurrence. Pin them down before entering the loops.

4. Read the dependencies, then shrink the space If only the last row or two is ever read, the $O(mn)$ table is unnecessary — unless you need to reconstruct how the edits were made, in which case you must keep it. The time-space trade, once more.

Summary

• DP is nothing but remembering subproblem answers; it takes naive recursion from $O(\varphi^n)$ to $O(n)$
• It applies when there is optimal substructure and overlapping subproblems; the real work is defining the state
• Knapsack is $O(nW)$ pseudo-polynomial — $W$ is a magnitude, not a count, so a large $W$ breaks it
• Edit distance fills a table with the $\min$ of three candidates: $O(mn)$ time, two rows of space
• WER, Viterbi, CTC, DTW, diffusion step selection — the same table keeps reappearing in production AI

Next: the operation that consumes almost all of AI's compute — the cost of matrix multiplication (The Cost of Matrix Multiplication).