Dynamic Programming

Some problems break into subproblems that repeat. The naive recursive Fibonacci function makes 331,160,281 calls to compute the 40th Fibonacci number, and among all those calls there are only 41 different questions. Dynamic programming answers each distinct subproblem once and keeps the answer, trading a table of memory for an exponential amount of time.

The same idea is how Lantern, the Millbrook Public Library's search service, knows that someone who typed "dispossesed" meant "dispossessed". The table that makes this work is small for one pair of words and ruinous for a million and a half, and the way Lantern keeps it small is the lesson of this topic: count the cells before writing the code.

Overlapping Subproblems

Computing fib(n) calls fib(n − 1) and fib(n − 2), and both of those call fib(n − 3), and the repeats compound level after level. The figure draws every call made by fib(6): 25 calls for only seven distinct arguments, 0 to 6. The subtree for fib(4) is computed twice, fib(3) three times and fib(2) five times. At fib(40), counted by running it, the total is 331,160,281 calls.

Divide and conquer, the first topic of this chapter, splits a problem into independent pieces that share nothing. Dynamic programming applies when the pieces overlap, and the overlap is what makes storing answers pay. Every repeated subtree in the figure is work that one stored number would replace.

Memoization: Remember on the Way Down

The first way to exploit the overlap keeps the recursive code as it is and caches each result by its arguments. In Python one standard decorator, functools.cache, does it, as Chapter 1 showed. The first call with a given argument computes the answer; every later call with the same argument is a dictionary lookup, the average constant-time operation from Chapter 5. With the cache in place, computing fib(40) takes 41 computations instead of 331 million calls.

Two costs remain. The cache holds one entry per distinct argument, which is memory that grows with the input. And the recursion is still recursion: measured on CPython 3.15, the memoized fib computes fib(900) and raises RecursionError on fib(1000), because the first call still descends a thousand levels before any answer is stored, and the default limit of 1,000 frames from Chapter 3 stops it.

The Table: Build From the Bottom Up

The second way turns the recursion inside out. Work out which subproblems each one depends on, then fill a table in an order that computes every dependency first, with a plain loop. For Fibonacci the order is left to right: fib(0), fib(1), fib(2) and onward, each the sum of the two before it. There is no recursion and no depth limit.

Often only the last row or two of the table is ever read again. Computing fib(10), which is 55, reads only fib(8) and fib(9), 21 and 34, so the loop can keep two numbers instead of a table and run in constant memory. That observation, that a dynamic program's memory is the part of the table still needed, is where most of its engineering happens.

Edit Distance

The edit distance between two words is the fewest single-letter insertions, deletions and substitutions that turn one into the other. It is computed in a table with a row for each letter of one word and a column for each letter of the other. Each cell holds the distance between two prefixes, and is the cheapest of three neighbours plus one: the cell above means a deletion, the cell to the left an insertion, and the cell diagonally up-left a substitution, which costs nothing when the two letters match.

The figure fills the table for "kitten" and "sitting". The first row and column count up from zero, the cost of building a prefix from nothing. The bottom-right cell is the answer, 3, and the shaded chain traces the cheapest route to it: substitute k with s, keep "itt", substitute e with i, keep n, insert g.

def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i]
        for j, cb in enumerate(b, 1):
            cur.append(min(prev[j] + 1,                # delete
                           cur[j - 1] + 1,             # insert
                           prev[j - 1] + (ca != cb)))   # substitute or keep
        prev = cur
    return prev[-1]

The function above fills the same table one row at a time and keeps only the previous row, since each cell reads only the row above it and the cell to its left. For each letter of the first word it builds a new row, taking the cheapest of the three neighbours for every cell. On CPython 3.15 it returns 3 for "kitten" and "sitting" and 1 for "dispossesed" and "dispossessed". Comparing two 12-letter words fills a 13 by 13 table, 169 cells.

Lantern's Typo Tolerance

Lantern matches a query term against an index term when their edit distance is 2 or less. Most of the table cannot matter for that question. A cell more than two steps from the diagonal already records more than two insertions or deletions, so only a band five cells wide around the diagonal can hold a value of 2 or below.

The figure shows the table for "dispossesed" against "dispossessed" with that band shaded. Every cell outside it is 3 or more, and the answer in the corner is 1: one inserted s. Three rules follow. Fill only the band. Skip any pair of words whose lengths differ by more than 2, because the corner then lies outside the band. And stop a comparison the moment every cell in a row exceeds 2, because no later row can come back down.

Even so, checking all 1.5 million index terms one by one costs about 50 band cells each, some 75 million cells for every query term, and autocomplete asks again on every keystroke after the second character. So Lantern walks its terms as the trie from Chapter 6. Terms that share a prefix share the rows for that prefix: one table row per trie edge, computed once for every term below it. A branch is abandoned as soon as its row passes 2, which is the pruning of the backtracking topic that follows. Search libraries compile the same limit further, into a Levenshtein automaton that is a state machine of the kind Chapter 14 describes.

What Dynamic Programming Costs

The table is the bill. Time is the number of cells times the work per cell, and memory is the number of cells kept. A full table comparing two files of 100,000 lines each would hold 10 billion cells, which is why diff tools use a different algorithm, published by Myers in 1986, whose cost grows with the length of the files times the number of differences, not with the product of the two lengths. Two nearly identical files are cheap to diff; two unrelated ones are not.

Counting cells before writing the code is the feasibility test. Rows times columns times the work per cell says whether the program finishes in a millisecond, a minute or never, and a bound on the answer, like Lantern's distance of 2, is the most common way to shrink that count by orders of magnitude.