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, or DP, turns problems the universe couldn't finish before it ends into problems your laptop finishes in a blink. And the whole trick is embarrassingly human: never solve the same sub-problem twice. Here's the plan. First we watch naive Fibonacci melt down into a million years of wasted work. Then we hand it a notebook and watch that million years collapse into microseconds. After that we turn the same move loose on coins, cargo, and text. The whole way through, we keep asking the one question 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 and decide in seconds whether DP fits. You'll name its state, write its recurrence, and fill a table that hands you the answer. That is 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, because in the traces you stepped naive Fibonacci (T29) and its memoised twin (T30). Look at the naive one and count what it does: fib(n) returns n when n < 2, and otherwise it returns fib(n-1) + fib(n-2). Those three honest lines are correct on every input you feed them. They are also a catastrophe, and watching why is the whole chapter in miniature.

Before we time anything, make sure the sequence itself is boring to you. The Fibonacci sequence starts 0, 1, and every later number is the sum of the two before it. So it runs 0, 1, 1, 2, 3, 5, 8, 13, 21. You can check any step in your head, because 5 + 8 = 13 and 8 + 13 = 21. Nothing about the arithmetic is hard, and that is exactly why it makes the perfect lab rat. When a three-line function takes a full second on maths this easy, the cost cannot be the adding. The cost is hiding in how the function calls itself, and that is where we point the microscope next.

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) — watch that: 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, and remember they were measured on a real machine, not imagined. Computing fib(35), which is one small number, cost 29,860,703 function calls. Push on to fib(40) and the bill climbs to 331 million. Now extrapolate honestly, using the exact count formula C(n) = 2·fib(n+1) − 1, and fib(100) works out to 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 of compute. (That is an order-of-magnitude figure, and timings are machine-dependent, but the scale is honest.) And all of it for a problem a child can do on paper.

So where is all that work actually going, call after call after call? Nowhere new. Trace the call tree for fib(5) and count the repeats with your own eyes: it asks for fib(3) twice, it asks for fib(2) three times, and it asks for fib(1) five times. The same tiny questions get re-asked and re-answered from scratch, every single time, all the way down the tree. That pattern of pure repetition is the first signal, and it has a name.

Signal one — overlapping sub-problems: the recursion keeps bumping into the same smaller problem again and again. Contrast that with merge sort from the divide-and-conquer chapter, which splits its input into fresh, non-overlapping halves. No sub-problem ever repeats there, so there is no DP needed. Signal two — optimal substructure: the best answer to the whole is built from best answers to its parts. fib(n) is literally fib(n-1) + fib(n-2), and the shortest route through a city is 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 at once, you are looking at a DP problem. And that means you are about to stop wasting a million years.

One honest aside before we fix anything, because the name trips everyone. Dynamic programming has nothing to do with typing code, and nothing especially dynamic is happening either. In the 1950s, "programming" meant planning with tables, the way a logistics officer programs a schedule. Bellman, by his own account, picked "dynamic" partly because it sounded impressive to the people funding his research. So don't search the name for meaning, because the meaning lives entirely in the method. A better private name is the one we will earn by the end of this chapter: write down every sub-answer, and never pay for it twice.

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

Keep a notebook, and the whole disaster disappears. The first time you compute fib(k), store the answer, and every later time, read it back instead of recomputing it. That habit is called memoisation, and it is 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 already in the notebook, hand it straight back. That one lookup is the line that kills the redundancy. Otherwise handle the two base cases, compute the two smaller Fibonaccis once, store the sum in memo[n], and return it. Each n from 0 up to the target gets filled exactly once and is only ever read after that. So the number of calls drops from exponential to just 2n − 1. That is 69 calls for fib(35) and 199 for fib(100). Same three-line logic, one extra dictionary, and an astronomically different bill. Measured on this machine, naive fib(35) took about 1.0 s and the memoised version about 18 microseconds. That is roughly a 50,000× gap, and while the timings are machine-dependent, the shape of the gap is not. One more gift: you don't even have to write the notebook by hand, because 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 in practice. Instead of recursing down and caching answers on the way back, you walk up from the bottom. You fill a table from the smallest sub-problem to the biggest, in an order where every value you need is already sitting there. That direction is called 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]

Look at what just vanished from the code: no recursion, no call stack, and no dictionary. What remains is one array, filled left to right, with each cell reading its two neighbours. That is O(n) time, and with two rolling variables it becomes O(1) space. It is the exact same recurrence as memoisation, simply run in the opposite direction.

Watch the table grow for fib(5) and the phrase "already sitting there" turns literal. Start the array with 0 and 1, the two base cases. Then each new cell is one addition over its two neighbours: 0 + 1 = 1, then 1 + 1 = 2, then 1 + 2 = 3, then 2 + 3 = 5. Five cells, five cheap additions, and nothing was ever computed twice. There is also a quietly practical reason to prefer this direction in Python. The memoised recursive version still stacks one frame per level, and CPython caps the call stack near 1000 frames by default. Ask top-down for fib(2000) and it dies with a RecursionError before the cache can save it. The bottom-up loop never touches the call stack at all, so it simply keeps walking.

you type
$ python memo_idioms.py

import functools, time

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

t0 = time.perf_counter()
print(fib(30), calls, round(time.perf_counter() - t0, 3))

calls = 0
@functools.cache                       # <-- the ONE line
def cfib(n):
    global calls; calls += 1
    return n if n < 2 else cfib(n - 1) + cfib(n - 2)

t0 = time.perf_counter()
print(cfib(30), calls, round(time.perf_counter() - t0, 6))
print(cfib.cache_info())
print(cfib(300) % 10 ** 9)
cfib.cache_clear()
print(cfib.cache_info())

# ---------- the same recurrence, bottom-up: a list you fill ----------
def fib_table(n):
    dp = [0, 1] + [0] * (n - 1)
    for k in range(2, n + 1):
        dp[k] = dp[k - 1] + dp[k - 2]
    return dp[n]

print(fib_table(30), fib_table(30) == fib(30))

# ---------- rolling: the table was only ever two cells wide ----------
def fib_rolling(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_rolling(30), fib_rolling(30) == fib_table(30))

# ---------- the sharp edge ----------
@functools.cache
def longest(seq):
    return len(seq)

try:
    longest([1, 2, 3])
except TypeError as e:
    print("TypeError:", e)
print(longest((1, 2, 3)))

you see
832040 2692537 0.391
832040 31 2.7e-05
CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)
990979600
CacheInfo(hits=0, misses=0, maxsize=None, currsize=0)
832040 True
832040 True
TypeError: unhashable type: 'list'
3

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, because that part is mechanical. The rare skill, the one interviewers actually probe, is turning a word problem into a table. And here is the good news: it is not inspiration but 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.

Let's run the recipe on coin change: given a set of coin values and a target amount, find the fewest coins that make the amount exactly. State: dp[a] is the fewest coins that can make amount a. Recurrence: to make a, the last coin you place is some c, and whatever remains is a − c, which we have already solved. So dp[a] = 1 + min(dp[a − c]), taken over every coin c ≤ a in the set. Base: dp[0] = 0, because it takes zero coins to make zero. Order: walk a from small to large, so every smaller answer exists before it is needed. Answer: when the table is full, read off 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 every other entry infinite, meaning "no way found yet". The outer loop walks the amounts upward, and the inner loop tries each coin as the final coin, keeping the cheapest option it finds. When it finishes, dp[6] = 2, and the two coins are the pair of 3s. Now notice what the table exposes about last chapter. Greedy would grab the biggest coin first and pay 4 + 1 + 1 = three coins, and it would lose. On the denominations [1,3,4], the locally-best move simply isn't the globally best one. DP never guesses a strategy: it quietly considers every possible last coin and remembers the winner.

Before you trust any of that, verify the little table by hand, because it only takes a minute. The coins are [1,3,4], so dp[1] is 1 and dp[2] is 2, built from 1-coins alone. dp[3] drops back to 1, because a single 3-coin beats three 1s. dp[4] is also 1, thanks to the single 4-coin, and dp[5] is 2, a 4-coin plus a 1. Then dp[6] lands on 2, the pair of 3s the code found. So the finished row from dp[0] to dp[6] reads 0, 1, 2, 1, 1, 2, 2, and every entry survived your own checking. That is the quiet superpower of DP tables: each cell is small enough to audit by hand.

from functools import cache

INF = float("inf")


def coin_min_memo(coins, amount):
    """Top-down: the recurrence, plus one decorator."""
    @cache
    def best(a):
        if a == 0:
            return 0
        if a < 0:
            return INF
        return min((best(a - c) + 1 for c in coins), default=INF)
    out = best(amount)
    return -1 if out == INF else out


def coin_min_table(coins, amount):
    """Bottom-up: the same recurrence, run in the other direction."""
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]


cases = [((1, 3, 4), 6), ((1, 2, 5), 11), ((2, 5), 3)]
for coins, amount in cases:
    m, t = coin_min_memo(coins, amount), coin_min_table(coins, amount)
    print(f"coins={coins} amount={amount:>3}  memo={m}  table={t}  agree={m == t}")

agree = all(coin_min_memo((1, 3, 4), a) == coin_min_table((1, 3, 4), a)
            for a in range(0, 201))
print("0..200 all agree:", agree)


# ---------- extra credit: WHICH coins, not just how many ----------
def coin_pick(coins, amount):
    dp = [0] + [INF] * amount
    last = [None] * (amount + 1)            # the winning coin for each amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c                 # remember WHY this cell won
    if dp[amount] == INF:
        return None
    out = []
    while amount:
        out.append(last[amount])            # walk the pointers backwards
        amount -= last[amount]
    return out


print(coin_pick((1, 3, 4), 6), coin_pick((1, 2, 5), 11), coin_pick((2, 5), 3))


# ---------- the actual run, python 3.12.7 ----------
#
# coins=(1, 3, 4) amount=  6  memo=2  table=2  agree=True
# coins=(1, 2, 5) amount= 11  memo=3  table=3  agree=True
# coins=(2, 5) amount=  3  memo=-1  table=-1  agree=True
# 0..200 all agree: True
# [3, 3] [1, 5, 5] None
#
#
# ---------- reading it ----------
#
# 1. (1, 3, 4) / 6 -> 2, and the coins are [3, 3]. That is the exact amount
#    greedy lost in chapter 39, where it paid 4 + 1 + 1. Nothing here is
#    cleverer than greedy -- it is only less willing to commit.
#
# 2. (2, 5) / 3 -> -1 in both directions. INF is doing real work: it means
#    "no way found yet", and min() carrying INF upward is how impossibility
#    propagates without a single special case in the loop.
#
# 3. default=INF on the generator matters. For a = 1 with coins (2, 5),
#    every c is larger than a, so best(a - c) is called with a negative a
#    and returns INF -- but if coins were EMPTY the generator would be
#    empty and min() would raise ValueError. default= is the guard.
#
# 4. Why reconstruction is easy in the table and awkward in the memo:
#    the table is a real array that OUTLIVES the fill, so last[] can sit
#    beside it and be walked backwards afterwards. The memo's answers live
#    inside a private dict on the closure; the path is implicit in a call
#    tree that has already collapsed and returned. To recover it you would
#    have to re-derive each step, or memoise the choice as well as the value.
#    Bottom-up keeps the evidence; top-down keeps only the verdict.
#
# 5. Both are O(amount x len(coins)) time. Space differs: the table is
#    O(amount) contiguous ints, the memo is O(amount) dict entries plus one
#    Python stack frame per level -- which is also why the memo is the one
#    that can hit RecursionError on a large amount.

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; 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.

Let's make it concrete with the exact cast the code below uses. The bag holds a budget of 4 kg, and the shelf holds four items: a guitar (1 kg, worth 1500), a laptop (3 kg, worth 2000), a stereo (4 kg, worth 3000), and a necklace (2 kg, worth 2500). Why not just try every subset and keep the best one that fits? With four items you honestly could, because 2⁴ is only 16 subsets. But the count doubles with every item you add, and doubling is the same exponential cliff Fibonacci fell off. At 40 items you are staring at 2⁴⁰, which is about 1.1 trillion subsets. So we will not enumerate subsets at all. We will fill a small grid instead, one cell per question.

To describe where you are mid-decision, the state needs two facts: which items you are still allowed to consider, and how much budget is left. State: dp[i][w] is the best value using only the first i items within a budget of w. Recurrence: for item i you make one binary choice. You either skip it and inherit dp[i-1][w], or, if it fits, you take it and score dp[i-1][w − weight_i] + value_i. Keep whichever of those two is larger. Base: zero items or zero budget means a value of 0. Answer: the final cell, 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, which builds in the base row and column for free. For each item at 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 from the remaining budget w − weight using the earlier items. Keep the max of the two. The final cell dp[4][4] comes out to 4000. And look at what won: the light, valuable pair (guitar + necklace), not the single 3000 stereo that a value-greedy grab might chase. Two nested loops give O(n·W) cells at O(1) each, so 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.

Hold the target in your hand before we build the machine. To turn kitten into sitting, substitute the k for an s, substitute the e for an i, and insert a final g. Walk it yourself: kitten → sitten → sittin → sitting, three edits, and no shorter path exists. Proving that "no shorter" claim by staring is the hard part, because edits interact in sneaky ways. An insert early in a word shifts every later letter, which changes what still needs fixing downstream. That is why we stop eyeballing whole words and let a table consider every prefix pair for us.

State: dp[i][j] is the edit distance between the first i letters of a and the first j letters of b. Recurrence: look only at the last letters of each prefix. If a[i-1] == b[j-1], they cost nothing, and the answer is just dp[i-1][j-1]. If they differ, you must pay for one edit, choosing the cheapest of three moves. You can delete a's last letter for dp[i-1][j] + 1, insert b's last letter for dp[i][j-1] + 1, or substitute one for the other at 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 of the grid.

Run one cell by hand and the recurrence loses its sting. Take dp[1][1], which compares the one-letter prefixes "k" and "s". The letters differ, so we pay one edit on top of the cheapest of the three neighbours: min(0, 1, 1) + 1 = 1. And that is obviously right, because turning "k" into "s" is a single substitution. Every one of the 56 cells in the table below is exactly this five-second calculation. The algorithm is not smart, it is relentless bookkeeping, and that is the whole secret.

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, then seed the first row and column with the "delete/insert everything" base costs. After that, fill each interior cell from its three neighbours: up is a delete, left is an insert, and up-left is a match or substitute, free when the letters agree. The bottom-right cell is the answer, and nothing else in the code is clever. Here is the actual table Python filled for kitten → sitting. Trace the diagonal of small numbers and you can literally read the alignment off the grid:

Now build it yourself: drag the slider and watch the grid fill in reading order, cell by cell. 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, and it is worth sitting with for a minute. Nothing here is clever per cell, yet the whole answer emerges from local moves almost too simple to respect.

Notice the human move that unlocked all of this. Comparing two whole strings head-on is hopeless, because there are far too many possible alignments. The insight was to stop comparing the wholes and compare all their prefixes instead. Once you know the distance for every shorter pair of prefixes, 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, in computer science, and in molecular biology. That triple discovery is no accident: 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. Two you'll meet constantly:

Longest common subsequence (LCS) is the longest run of characters appearing in both strings in order, though not necessarily adjacent. Its state is edit distance's cousin: dp[i][j] is the LCS length of the first i of a and the first j of b. If the last letters match, take dp[i-1][j-1] + 1, and otherwise take 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. The state has a twist worth pausing on: dp[i] is the length of the longest increasing subsequence ending at index i. The recurrence is dp[i] = 1 + max(dp[j]), taken 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 from the run above. At index 6, holding value 101, the best increasing run ending there is length 4, because it chained through 2, 5, 7. The final answer is the max over the whole array, not the last cell. That approach is O(n²) here, since each cell scans all the earlier cells. A sharper version uses binary search (the searching chapter) to reach O(n log n). Take that as 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 if you take away one practical move for finding the state, take this one. Every recurrence in this chapter came from the same question: what was the last decision? For coin change it was the last coin, for knapsack it was skip-or-take on item i, and for edit distance it was fixing the last letters. Naming that decision tells you what the state must record, because the state describes the leftover problem. So when a new problem stares back blankly, don't hunt for the table first. Ask what the final move could be, and the table tends to introduce 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)). In other words, the recurrence tells you not just the answer but exactly how little you need to remember.

So the arc of this chapter really is a single sentence. Spot the overlap, define the state, write the recurrence, and fill the table. Do that, and a problem that would outlast the universe finishes before your coffee cools. That is dynamic programming, and it is, more than any other single idea in this volume, 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. →