40Dynamic programming — remember to win

In Chapter 39 we let greedy grab the best-looking move and never look back. That was dazzling when we could prove it was right, and quietly wrong when we couldn't. Here we meet the algorithm that never has to gamble. Dynamic programming — DP — takes problems the universe couldn't finish before it ends and turns them into problems your laptop finishes in a blink. The whole trick is embarrassingly human: never solve the same sub-problem twice. Here's the plan. We'll watch naive Fibonacci melt down into a million years of wasted work, hand it a notebook, and see that million years collapse into microseconds. Then we turn the same move loose on coins, cargo, and text. The whole way through we keep asking the one thing that matters: what is the smallest sub-problem I keep re-solving, and what if I just wrote its answer down? By the end you'll look at a fresh problem, decide in seconds whether DP fits, name its state, write its recurrence, and fill a table that hands you the answer. That's the exact skill that separates the engineer the interviewer remembers from the one they forget.

01The two signals that scream "dynamic programming"

Let's start where you already stand. In the traces you stepped naive Fibonacci (T29) and its memoised twin (T30). Look at it: three honest lines. fib(n) returns n when n < 2, and otherwise returns fib(n-1) + fib(n-2). It is correct. It is also a catastrophe, and watching why is the whole chapter in miniature.

Count the calls, don't guess them. Let C(n) be the number of times fib is invoked to compute fib(n). Every call either stops immediately (n < 2) or spawns two more, so C(n) = 1 + C(n-1) + C(n-2). Notice what that means: the count itself grows like Fibonacci. The tree of calls nearly doubles at every level, and that is the definition of exponential. Here is the real toll, measured, not imagined:

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

for n in [30, 35, 40]:
    calls = 0; v = fib(n)
    print(n, v, calls)
# 30 832040    2692537
# 35 9227465   29860703
# 40 102334155 331160281

Read those counts. Computing fib(35), one small number, cost 29,860,703 function calls. Push to fib(40) and it is 331 million. Extrapolate honestly (the count formula is C(n) = 2·fib(n+1) − 1) and fib(100) would take about 1.15 × 10²¹ calls. At the roughly 30 million-calls-per-second this machine managed, that is on the order of a million years (order-of-magnitude; timings are machine-dependent). All for a problem a child can do on paper.

Where is all that work going? Nowhere new. The tree for fib(5) asks for fib(3) twice, fib(2) three times, and fib(1) five times. They are the same tiny questions, re-asked and re-answered from scratch, over and over. That is the first signal, and it has a name.

Signal one — overlapping sub-problems: the recursion keeps bumping into the same smaller problem. (Contrast merge sort back in the divide-and-conquer chapter. It splits into fresh, non-overlapping halves, so there are no repeats and no DP needed.) Signal two — optimal substructure: the best answer to the whole is built from the best answers to its parts. fib(n) is literally fib(n-1) + fib(n-2), and the shortest route through a city is the shortest route to here plus one more step. Richard Bellman, who developed DP in the 1950s, called this the principle of optimality. When both signals fire, you are looking at a DP problem, and you are about to stop wasting a million years.

02Two directions, one idea: memoise down, tabulate up

Keep a notebook. The first time you compute fib(k), store it. Every later time, read it back instead of recomputing. That's memoisation, or top-down DP: still recursive, but each distinct sub-problem is solved exactly once. Count the calls again and the collapse is total.

def fib_memo(n, memo):
    if n in memo:            # already solved? read it back — O(1)
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]           # write the answer down before returning

# fib_memo(35, {}) makes 69 calls, not 29,860,703.
# fib_memo(100, {}) makes 199 calls — the "million years" becomes microseconds.

Line by line: if n is in the notebook, hand it back. That is the line that kills the redundancy. Otherwise handle the two base cases, then compute the two smaller Fibonaccis once, store the sum in memo[n], and return it. Each n from 0 to the target gets filled exactly once and is then only ever read. So the number of calls drops from exponential to 2n − 1: 69 calls for fib(35) and 199 for fib(100). Same three-line logic, one dictionary, an astronomically different bill. Measured on this machine, naive fib(35) took about 1.0 s and the memoised version about 18 microseconds, roughly a 50,000× gap (machine-dependent, but the shape of the gap is not). You don't even have to write the notebook by hand: Python's @lru_cache from functools (Volume 1 ch11) bolts this exact memoisation onto any function with one line.

There is a second way to hold the same idea, and it is often the better one. Instead of recursing down and caching on the way back, walk up. Fill a table from the smallest sub-problem to the biggest, in an order where every value you need is already sitting there. That's tabulation, or bottom-up DP.

def fib_table(n):
    dp = [0, 1] + [0]*(n-1)          # dp[k] will hold fib(k)
    for k in range(2, n+1):
        dp[k] = dp[k-1] + dp[k-2]    # both already filled — just read them
    return dp[n]

No recursion, no call stack, no dictionary: just one array, filled left to right, each cell reading its two neighbours. It's O(n) time and, with two rolling variables, O(1) space. It's the same recurrence as memoisation, run in the opposite direction.

So the fix is a notebook. But Fibonacci handed us the recurrence for free. The real skill — the thing that actually separates people — is inventing the recurrence for a problem nobody wrote down for you. There's a procedure for that. →

03The recipe: name the state, write the recurrence

Everyone can memoise a function someone else wrote. The rare skill is turning a word problem into a table. It is not inspiration. It is a five-step procedure you can run on anything:

1. Define the state. Decide what a sub-problem is, and write down in one plain sentence what dp[…] means. This is 80% of the work. Get it right and the rest falls out.
2. Write the recurrence. Express dp[state] using strictly smaller states — the same "best of parts" the problem's optimal substructure promised.
3. Fix the base cases. The smallest states you can answer with no recurrence at all.
4. Choose the fill order. Any order where a cell's dependencies are computed before it.
5. Read off the answer. Name the cell that holds it.

Run it on coin change: given coin values and a target amount, what is the fewest coins that make the amount? State: dp[a] = the fewest coins that make amount a. Recurrence: to make a, the last coin is some c, and whatever's left is a − c, which we've already solved. So dp[a] = 1 + min(dp[a − c]) over every coin c ≤ a. Base: dp[0] = 0 (zero coins make zero). Order: a from small to large. Answer: dp[amount].

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF]*amount          # dp[0]=0; the rest "unknown"
    for a in range(1, amount+1):
        for c in coins:              # try every coin as the LAST coin
            if c <= a:
                dp[a] = min(dp[a], dp[a-c] + 1)
    return dp

print(min_coins([1,3,4], 6))
# [0, 1, 2, 1, 1, 2, 2]  ->  dp[6] = 2   (that's 3+3)

Line by line: dp starts with dp[0]=0 and everything else infinite ("no way found yet"). The outer loop walks amounts upward, and the inner loop tries each coin as the final coin and keeps the cheapest option. When it finishes, dp[6] = 2: two coins, the pair of 3s. Notice what the table exposes. Greedy (last chapter) would grab the biggest coin first, 4 + 1 + 1 = three coins, and lose. On the denominations [1,3,4] the locally-best move isn't globally best. DP doesn't guess a strategy. It quietly considers every last coin and remembers the winner.

Coin change had a one-dimensional state — a single number a. Some problems need the table to grow a second axis. That's where DP starts to feel like real power. →

040/1 knapsack — the value-under-a-budget grid

Here's the setup. You have a weight budget and a set of items, each with a weight and a value. Take each item once or not at all, and maximise total value without blowing the budget. This is the shape of a thousand real decisions: which features fit in a sprint, which trades fit a risk limit, which files fit on the disk. Greedy by "best value-per-kilo" can fail here too. DP cannot.

The state needs two facts: which items you're allowed to consider, and how much budget is left. State: dp[i][w] = the best value using only the first i items within a budget of w. Recurrence: for item i you make one binary choice. Either skip it (dp[i-1][w]) or, if it fits, take it (dp[i-1][w − weight_i] + value_i), and keep the larger. Base: zero items or zero budget → value 0. Answer: dp[n][W].

items = [("guitar",1,1500), ("laptop",3,2000),
         ("stereo",4,3000), ("necklace",2,2500)]   # (name, weight, value)
W = 4
wt  = [w for _,w,_ in items]; val = [v for _,_,v in items]; n = len(items)
dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        dp[i][w] = dp[i-1][w]                         # skip item i
        if wt[i-1] <= w:                              # if it fits, try taking it
            dp[i][w] = max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1])

print(dp[n][W])   # 4000  — guitar (1kg,1500) + necklace (2kg,2500)

Line by line: dp is an (n+1) × (W+1) grid of zeros, the base row and column. For each item and each budget, first assume we skip it and inherit the answer from the row above. Then, if the item fits, compare against taking it: its value plus the best we could do with the remaining budget w − weight using the earlier items. Keep the max. The final cell dp[4][4] is 4000, and it's the light, valuable pair (guitar + necklace), not the single 3000 stereo that a value-greedy grab might chase. Two nested loops, O(n·W) cells, each O(1): the whole grid is one cheap sweep.

Coin change and knapsack both optimised a number. The most beautiful DP of all optimises something you touch every hour without noticing: the distance between two pieces of text. →

05Edit distance — the algorithm inside diff, spell-check, and DNA

How different are two words? Let's define it precisely. The edit distance (Levenshtein distance) between strings a and b is the minimum number of single-character inserts, deletes, and substitutions to turn one into the other. "color" → "colour" is 1 (insert a u). "kitten" → "sitting" is 3. And the way we compute it is the same table-filling move, now on a grid.

State: dp[i][j] = the edit distance between the first i letters of a and the first j letters of b. Recurrence: look at the last letters. If a[i-1] == b[j-1], they cost nothing, so the answer is dp[i-1][j-1]. If they differ, you must do one edit, and you take the cheapest of three moves: delete a's last letter (dp[i-1][j] + 1), insert b's last letter (dp[i][j-1] + 1), or substitute (dp[i-1][j-1] + 1). Base: turning a length-i word into the empty string costs i deletes, so dp[i][0] = i and dp[0][j] = j. Answer: the bottom-right cell.

def edit_distance(a, b):
    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        # a[:i] -> ""  costs i deletes
    for j in range(n+1): dp[0][j] = j        # "" -> b[:j]  costs j inserts
    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)   # match / substitute
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3
print(edit_distance("recieve", "receive"))  # 2   (the classic typo)
print(edit_distance("color",   "colour"))   # 1

Line by line: build the grid, seed the first row and column with the "delete/insert everything" base costs, then fill each interior cell from its three neighbours: up (delete), left (insert), and up-left (match or substitute, free if the letters agree). The bottom-right cell is the answer. Here is the actual table Python filled for kitten → sitting. Trace the diagonal of small numbers and you can literally read the alignment:

Now build it yourself. Drag the slider and watch the grid fill in reading order. Each interior cell lights up its three source neighbours and shows the exact min(…) it evaluates. This is the "fill the grid" mental model made physical. Nothing here is clever per cell; the whole answer emerges from local moves.

Notice the human move that unlocked all of this. Comparing two whole strings is hopeless: there are too many alignments. The insight was to stop comparing the wholes and compare all their prefixes instead. Once you know the distance for every shorter pair, the full pair is one cheap step away. That reframing — "solve it for all smaller versions and the big version is trivial" — is the beating heart of DP. It was independently discovered in linguistics, computer science, and molecular biology, because it is simply how this class of problem wants to be solved.

06Two more shapes: common subsequence & increasing subsequence

Once you can spot the state, new problems stop feeling new. Here are two you'll meet constantly:

Longest common subsequence (LCS) is the longest run of characters appearing in both strings in order (not necessarily adjacent). Its state is edit distance's cousin: dp[i][j] = LCS length of the first i of a and first j of b. If the last letters match, it's dp[i-1][j-1] + 1, otherwise max(dp[i-1][j], dp[i][j-1]). This is the engine of git diff: the unchanged lines between two file versions are exactly their LCS, and everything else is an add or a delete.

Longest increasing subsequence (LIS) is the longest run of values that increases, picked from a list in order. State: dp[i] = the length of the longest increasing subsequence ending at index i. Recurrence: dp[i] = 1 + max(dp[j]) over every earlier j with seq[j] < seq[i]. Both were run in Python:

lcs("ABCBDAB", "BDCAB")            # length 4  -> "BCAB"
lis([10, 9, 2, 5, 3, 7, 101, 18]) # length 4  -> [2, 5, 7, 101]
# per-index dp for LIS: [1, 1, 1, 2, 2, 3, 4, 4]

Read the LIS dp array: at index 6 (value 101) the best increasing run ending there is length 4, chained through 2, 5, 7. The answer is the max over the whole array. That's O(n²) here, because each cell scans all earlier cells. A sharper version uses binary search (the searching chapter) to reach O(n log n), a preview of how one technique feeds the next.

You've now filled five different tables with one procedure. Time to name the mental move you actually installed — and know exactly when it will and won't save you. →

07When to reach for it — and the move you keep

Reach for DP when both signals fire: overlapping sub-problems (you keep re-solving the same smaller thing) and optimal substructure (the best whole is built from best parts). Miss either and DP is the wrong tool. No overlap? You have plain divide-and-conquer (the halving chapter); merge sort gains nothing from a memo because its halves never repeat. No optimal substructure? Neither greedy nor DP is guaranteed, and you may be forced to search everything (the backtracking chapter).

It helps to place DP among its neighbours. Divide-and-conquer splits into independent pieces and never looks back. Greedy (last chapter) commits to the best-looking move and never reconsiders: fast when it's provably right, wrong on [1,3,4] coins. DP is the careful middle. It considers every choice like brute force, but remembers each sub-answer so it pays for each only once. That's why the one-liner for DP is "brute force that doesn't repeat itself."

And here is the space bonus most people skip. Once you have the recurrence, look at what each cell actually depends on. Fibonacci's dp[k] needs only the last two cells, so keep two variables and drop O(n) memory to O(1). Edit distance's row i depends only on row i-1, so keep one row and drop O(m·n) space to O(min(m,n)). The recurrence tells you not just the answer but exactly how little you need to remember.

So the arc of this chapter is a single sentence: spot the overlap, define the state, write the recurrence, fill the table, and a problem that would outlast the universe finishes before your coffee cools. That is dynamic programming. More than any other single idea in this volume, it is the one interviewers use to separate the 1% from the rest.

DP works only when sub-problems overlap. But what about the problems where they don't — where every path is unique and the tree of choices is astronomically wide, yet most branches are hopeless the moment you start them? Next: recursion & backtracking — how to search a giant tree of choices, and how pruning a doomed branch turns "explores a billion dead ends" into "explores a thousand live ones." DP was backtracking that remembered; the next chapter is backtracking that knows when to quit. →