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.