Remember instead of recomputing

The last chapter ended on the weak spot of divide and conquer. The recursive fib(40) makes 331 million calls, although only 41 of their arguments are different: the same subproblems are solved again and again. The cure suggests itself: remember the answers you already have. Out of this thought grows a tool that everyone who types text relies on. We’ll build two programs. One answers the word “seperate” with “Did you mean: separate?” The other shows how two versions of a text differ, like the Text diff page on this site. Both rest on one technique with an odd name, chosen so as not to annoy a Secretary of Defense.

The job: a typo

What does it mean for one word to look like another? Typos come in three kinds: an extra letter, a missing letter, a wrong letter. From “seperate” to “separate” is one substitution, from “cat” to “scat” one insertion. The fewer such edits it takes to fix a word, the closer it is to the right one. Then the suggestion “Did you mean…” is the dictionary word that takes the fewest edits.

The first idea is to try every possible edit of the typo and see which of the resulting strings are in the dictionary. For a single edit that works. How many strings does one edit make out of “seperate,” and how many do two?

One edit gives 435 strings, two already 88 thousand: every further edit multiplies the number of variants by hundreds, and three edits would give millions of strings. And a long word can easily hold three or four typos. We have to come at it from the other end: take each dictionary word and count how many edits separate it from the typo. For that we need a function for the distance between two words, and a fast one: a dictionary holds tens of thousands of words. It will take several parts to build.

Part one: memory

Remember the recursive fib from Chapter 9. It is correct, but a call to fib(n) computes fib(n - 2) all over again, although it was already computed inside fib(n - 1). The fix is a dictionary: before computing, look in it, and once you have computed, write the answer there.

The answer comes at once, although recursion without memory would take longer than a human lifetime to get it (we estimated that in Chapter 13). Press “Steps”: each fib(k) is computed once, and every repeated call leaves straight away with the answer from the dictionary. There are 89 different subproblems (fib(2) to fib(90)), one addition each, and the time has gone from exponential to linear.

This technique is called memoization, from “memo”: in 1968 the British artificial-intelligence researcher Donald Michie called such functions memo functions. In Python you don’t have to write it by hand: the decorator functools.cache, which we promised in Chapter 10, keeps such a dictionary itself, with the call’s arguments as the key.

Memory comes with two conditions. The function must be pure: for the same arguments it returns the same thing and changes nothing around it, otherwise a remembered answer will one day turn out wrong. And the arguments must be usable as dictionary keys: numbers, strings, tuples, but not lists (why, see Chapter 16).

There is a third difficulty, less visible. Try fib(3000) in the cell above: Python answers RecursionError. The first call, fib(3000), knows nothing yet and goes down for fib(2999), which goes down for fib(2998), and the call stack grows by three thousand frames, while Python allows about a thousand (Chapter 9). Memory saved us from repetition, but not from depth. We need a way to compute in the other direction, from the bottom up.

Part two: the table

Recursion with memory works from the top: from the question to subquestions, until it reaches the simple ones. But you can start with the simple ones and climb, filling a table of answers in order. Then, by the time an answer to a subproblem is needed, it is already in the table. For Fibonacci the table is a list, and we get the loop we already wrote in Chapter 9. More interesting is a problem where the table is not so easy to guess.

A flight of ten steps leads to the second floor. You may go up one step at a time or two at once. In how many ways can you climb it? Think about the last step. You can reach the tenth step either from the ninth (a step of one) or from the eighth (a step of two). So the number of ways to reach the tenth is the number of ways to reach the ninth plus the number for the eighth. And the same goes for every step.

For ten steps there are 89 ways, for a hundred a number with 21 digits, and all of it in a hundred additions. Listing every way up a hundred-step staircase would never end; the table computes the answer without listing a single one. You have probably recognized the numbers: 1, 1, 2, 3, 5, 8… are Fibonacci under another name. Allow a step of three and a third term appears, and the numbers change: try it.

The loop in this program is secondary. The whole of it rests on one sentence: the answer for step k is made of the answers for lower steps. Such a rule is called a transition, and one question helps you invent transitions: what was the last step? The same question will help on a map of a city.

Routes across a city

Streets divide a city into square blocks. A courier has to get from the top-left corner to the bottom-right one, going only right or down; any other move would make the route longer. How many different routes are there? Ask about the last step again: you can arrive at a crossing either from above or from the left. So the number of routes to a crossing is the sum of the numbers for the neighbor above and the neighbor to the left. Along the top street and the left column there is a single route: straight ahead all the way.

With every crossing open, the numbers form Pascal’s triangle turned on its side. The number of routes across a grid of $m$ by $n$ blocks is $\binom{m+n}{m}$: a route is $m + n$ steps, and you choose which $m$ of them go down (in our math course this problem is solved by a rook going home). But close a single crossing and the formula stops working. The table doesn’t care: it writes zero for the closed crossing and carries on. Here it is in code; a hash sign marks a closed crossing.

The order of the walk matters here: rows from top to bottom, and within a row from left to right. Then, by the time a cell is computed, its neighbors above and to the left are ready. That is what a bottom-up table is about: choose an order in which every subproblem comes after the ones it depends on. For the staircase the order is by increasing step, for the city by rows. Recursion with memory finds such an order by itself, at the cost of a deep stack; a table makes you think about the order in advance, but it never runs into the recursion limit and usually works faster.

RAND, the 1950s: a name for the Secretary

The technique assembled from these two parts has a name, and behind the name is one of the best-known stories in computing. The man who chose it told the story himself; we retell it after him.

Historians point out that the story doesn’t fit the dates. Bellman places it in the fall of 1950, but Wilson became Secretary of Defense in January 1953, and Bellman’s papers with the words “dynamic programming” were appearing before that. Perhaps memory shifted the events, or perhaps the story was polished by years of retelling. Either way, the name stuck. Dynamic programming is a way to solve problems that reduce to smaller subproblems, where the same subproblems come up many times: each is solved once and its answer remembered, from the top (recursion with memory) or from the bottom (a table).

What sets it apart from divide and conquer in the last chapter is only this repetition. Merge sort splits a list into halves that don’t overlap, and there is nothing to remember: each half comes up once. For the staircase and the city the subproblems overlap: the answer for a crossing is needed both by its right neighbor and by the one below. Where there are few subproblems and many repetitions, dynamic programming wins.

Part three: the till

Now a problem where it is easy to go wrong even when you know the technique. In how many ways can you make 5 cents out of coins of 1, 2 and 5 cents? Reasoning “by the last step” suggests a transition: the last coin could have been a one, a two or a five, so ways[s] = ways[s - 1] + ways[s - 2] + ways[s - 5]. We compute it and compare the result with an answer obtained another way.

Nine against four. Write them out by hand: 5; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1. Four ways. The first function counted more because it counts sequences: for it, 2 + 2 + 1, 2 + 1 + 2 and 1 + 2 + 2 are three different ways, since the coins come in a different order. For the staircase that was right, because the order of steps matters there, but not for a purse.

The second function is cleverer: first it counts the ways using only ones, then it allows twos, then fives. The coins are added kind by kind, and every set of coins is counted once, in the order “all the ones first, then all the twos.” A transition has to match what we count as different, no more and no less. A dollar in coins of 1, 2, 5 and 10 cents can be made in 2,156 ways; the first function would count about $1.2 \cdot 10^{23}$.

A cashier, though, needs a single way, the shortest one: change in the fewest coins. This is a problem about an optimum, and the transition changes: a minimum instead of a sum. If the last coin of the best change is $c$, then the coins before it must be the best change for $s - c$. Try every possibility for the last coin and take the best:

$$\mathit{best}(s) = 1 + \min_{c \le s} \mathit{best}(s - c), \qquad \mathit{best}(0) = 0.$$

Besides the table best the program keeps a second one, last: which choice gave the best answer. From it the answer is recovered backward, from the amount down to zero, one coin per step. This is a general technique: the table of numbers tells you how many, the table of choices how. Without it we would know that 88 cents takes eleven coins but not which ones. More interesting is 13 cents in twos and fives: two fives would make shorter change, but the remaining 3 cents can’t be made of twos, and the table finds 2 + 2 + 2 + 2 + 5. And 3 cents can’t be made of such coins at all.

It remains to see why the minimum over the best change for smaller amounts gives the best change for a bigger one. Suppose the last coin of the best change for $s$ is $c$. The other coins make $s - c$. If $s - c$ could be made with fewer coins, we would put those in instead and get change for $s$ better than the best—a contradiction. So an optimal solution contains optimal solutions of its subproblems. This property is called optimal substructure, and it is what lets you build an optimum out of optima. Without it a table of best answers is useless. You can’t find the longest path without repeats in a graph this way, for example: the continuation of a long path may run into vertices its beginning has already used.

Part four: the rucksack

One night a burglar breaks into an antique shop. The rucksack holds 10 kilograms, and on the shelves are a samovar, a clock, a painting and five more things, each with its own weight and price. What should go into the rucksack for the richest haul? Try it yourself before reading on.

This problem differs from the till. There are as many coins of each kind as you like, but there is only one samovar: once taken, it can’t be taken again. So a sum alone isn’t enough for a subproblem; it must also remember which things have been considered. Put the things in a row and decide, starting from the first, whether to take each one. A subproblem is a pair of numbers: “the best haul from the first $i$ things with capacity $w$.” For the $i$-th thing, of weight $m_i$ and price $p_i$, there are two options: leave it, and the answer is the same as for $i - 1$ things; or take it, if it fits, and its price is added to the best haul from the first $i - 1$ things in the remaining $w - m_i$ kilograms:

$$\mathit{best}(i, w) = \max\bigl(\mathit{best}(i-1, w),\; p_i + \mathit{best}(i-1, w - m_i)\bigr).$$

The most expensive thing, the samovar, doesn’t make it into the best rucksack, and “most expensive first” loses here: the samovar and the clock give 50, while the painting, the figurine, the book and the casket give 54. Recovery again runs from the end: if the answer in cell $(i, w)$ differs from the answer without the $i$-th thing, the thing was taken, and the capacity shrinks by its weight.

The table here has $n + 1$ rows and $W + 1$ columns, and the work is of the order of $n \cdot W$. With eight things and ten kilograms that is 99 cells against $2^8 = 256$ sets to try by brute force, and with a hundred things brute force is hopeless: $2^{100}$ sets. But there is a catch: give the weights in grams and there are a thousand times more columns, though the problem is the same. The time depends on how large the numbers in the input are, not only on how many there are, and for weights with twenty digits the table won’t help. Whether the knapsack has a method that is fast for any weights, nobody knows: it is one of the problems Chapter 57 will be about.

Part five: a subsequence

To compare texts we need one more notion. From the word “planet” you can strike out letters and get “plan” or “pant”: the remaining letters keep their order but needn’t stand together. The result of such striking out is called a subsequence. A substring from Chapter 7 is the special case where you may strike out only at the edges.

A classic makes a good warm-up: find the longest increasing subsequence in a row of numbers, say in the digits of $\pi$. The subproblem: “the length of the longest increasing subsequence that ends at element $i$.” The transition: such a subsequence is element $i$ attached to the best subsequence that ends at some smaller element to its left. The answer is the best of them all.

The double loop takes of the order of $n^2$ steps. There is a faster way, built on binary search from Chapter 20. Keep a list tails: tails[k] is the smallest last element an increasing subsequence of length $k + 1$ can end with. This list is always increasing, and every new number either lengthens it or lowers one of the tails, the one whose place bisect_left finds. That makes $n \log n$.

In a random permutation of $n$ numbers the longest increasing subsequence comes out a little shorter than $2\sqrt{n}$. Stanislaw Ulam asked about this length in 1961, and in 1977 Anatoly Vershik and Sergei Kerov proved that it grows as $2\sqrt{n}$; the lower bound was obtained at the same time, independently, by Benjamin Logan and Lawrence Shepp. But we need subsequences for something else: they are the language in which texts are compared. We’ll come back to that after one more part.

Part six: a distance between words

Edit distance, or Levenshtein distance, is the measure for typos we were looking for. The subproblem is the distance between the beginnings of the words: the first $i$ letters of word $a$ and the first $j$ letters of word $b$. And once again the question about the last step: what became of the last letter? There are three options.

• The last letter of $a$ was deleted: it remains to turn the first $i - 1$ letters of $a$ into the first $j$ letters of $b$, plus one edit.
• The last letter of $b$ was inserted at the end: it remains to turn $i$ letters of $a$ into $j - 1$ letters of $b$, plus one edit.
• The last letter of $a$ became the last letter of $b$: free if they are the same, otherwise it is a substitution, one edit. What remains is $i - 1$ and $j - 1$.

$$d(i, j) = \min\bigl(d(i-1, j) + 1,\; d(i, j-1) + 1,\; d(i-1, j-1) + [a_i \ne b_j]\bigr), \qquad d(i, 0) = i,\; d(0, j) = j.$$

The square brackets mean one if the letters differ and zero if they are the same. The edges of the table are clear: an empty beginning turns into $j$ letters by $j$ insertions, and $i$ letters into nothing by $i$ deletions. First we write the formula as a plain recursion and count the calls, then add one line with cache.

Nearly nine hundred thousand calls against 90. There are as many different subproblems here as there are pairs “a beginning of the first word, a beginning of the second”: $10 \cdot 9 = 90$, while recursion without memory goes through them hundreds of thousands of times. The table is easiest to fill like the courier’s city, row by row, because it is such a city. Put the letters of the first word down the left edge and those of the second along the top. A step down deletes a letter, a step right inserts one, a diagonal step keeps a letter (free) or substitutes it (one edit). Every way to turn one word into the other is a path from the top-left corner to the bottom-right one, and the distance is the price of the cheapest path.

Recovery here works as in the till and the rucksack: walk back from the bottom-right corner, each time asking which neighbor a cell got its value from. The path back is the recipe of edits, only in reverse. The table has $(m + 1)(n + 1)$ cells with three comparisons each, so the time is of the order of $m \cdot n$. For the distance alone, without the edits themselves, you don’t need to keep the whole table: each row depends only on the one before. Here is the working function we’ll use from now on.

Assembly: “Did you mean…”

We have enough parts. The dictionary comes from War and Peace: every word of the novel, cut up by the function words from Chapter 7, with the number of times each occurs (a Counter from Chapter 8). We keep only words made of plain Latin letters (and hyphens): that drops the French words with accents and the contractions with apostrophes. For a typo we compute the distance to every dictionary word and keep the closest. If several are equally close, we offer the most frequent first, since it is the likeliest. And one saving: words whose length differs from the typo’s by more than two can’t be closer than two edits, so we needn’t compare them.

Try “seperate”, “moskow”, “napolean”, “natasa”: the program copes, and each word takes a fraction of a second. “Hello” fares worse: the program offers “hullo”. The code has no bug: the translation of War and Peace never uses the word “hello,” and the program knows only its own dictionary. “Recieve” turns into “relieve” rather than “receive”: to the program, swapping “ie” for “ei” costs two edits, while “relieve” is a single substitution away. A person sees at once that two neighboring letters have changed places, a very common slip; the program counts every edit the same. And “telephone” becomes “telescope” or “elephant”: there are no telephones in an 1869 novel, the nearest words are three edits away, and the suggestion no longer makes sense.

The spelling checkers in word processors and phones rest on the same measure, with corrections for these three troubles. Their dictionary is large and modern. Edits weigh differently: replacing a letter with one on a neighboring key, or one vowel with another, costs less than replacing distant letters. A fourth kind of edit is counted: swapping two neighboring letters, as in “recieve.” Fred Damerau introduced it in 1964: by his count, more than 80% of typos are a single insertion, a single deletion, a single substitution or a single swap. And suggestions further than two edits away are usually not offered at all. All of these are corrections to the transition; the table stays the same.

Assembly: what changed

The second program compares two versions of a text. Here it is handier to think about what stayed the same. What two versions have in common is their longest common subsequence: the longest chain that can be obtained by striking out from the first version and from the second. Everything that didn’t get into it was deleted in the first version and added in the second. The transition is again about the last elements: if they are equal, they extend the common subsequence of the beginnings; if not, at least one of them won’t get in, and we take the better of the two options.

$$L(i, j) = \begin{cases} L(i-1, j-1) + 1, & a_i = b_j, \\ \max\bigl(L(i-1, j),\, L(i, j-1)\bigr), & a_i \ne b_j. \end{cases}$$

It is a relative of Levenshtein distance: forbid substitutions and allow only insertions and deletions, and the distance between strings of lengths $m$ and $n$ is exactly $m + n - 2L(m, n)$. You can compare letters, words or whole lines: the table doesn’t care what it compares, as long as elements can be tested for equality. Programs that compare texts usually compare lines.

This is how the core of the program diff works. It appeared in Unix in 1974, and in 1976 its authors, James Hunt and Douglas McIlroy of Bell Labs, described their algorithm: it finds the same common subsequence of lines, but more economically than a full table. The economy is needed: two files of a hundred thousand lines each would make a table of ten billion cells. In 1986 Eugene Myers found an algorithm whose time depends on the size of the files multiplied by the number of differences. Versions of a file usually differ only a little, so in practice it runs in nearly linear time. Git uses it by default; the diff-match-patch library is built on it, and the text comparison page of this site runs on that library. Git also has a --patience mode: it first finds the lines that occur only once in each version and lines them up by the longest increasing subsequence from part five.

How to recognize dynamic programming

The six parts were built by one recipe, and it is worth writing down. A problem asks for dynamic programming if its answer can be assembled from the answers to the same problems of a smaller size and those smaller problems repeat. Then come five questions.

1. What is the subproblem? Usually it is a beginning of the input: the first $k$ steps, the first $i$ things, the first $i$ letters of one word and $j$ of the other. The subproblem must remember everything needed for the solution: for the rucksack, a sum alone wasn’t enough.
2. What is the transition? Ask what the last step was, and go through all the options: the last coin, take the thing or not, what became of the last letter.
3. Where is the base? The smallest subproblems, whose answer is obvious: zero steps, an empty word.
4. In what order to fill? So that every cell is computed after the ones it depends on. Or leave the order to recursion with @cache, if the stack can take its depth.
5. How to recover the answer? Remember the choice in each cell, or walk back from the corner asking where each value came from.

The running time is the number of subproblems times the number of options in the transition. The staircase has $n$ subproblems with two options each, Levenshtein $m \cdot n$ subproblems with three, the rucksack $n \cdot W$ with two. The recipe fails if the subproblems don’t repeat (then divide and conquer is enough), if there is no optimal substructure (as with the longest path without repeats), or if there are too many subproblems: for the traveling salesman problem of Chapter 58 their number grows as $n \cdot 2^n$.

In the longest increasing subsequence problem the subproblem was “the best length that ends at element $i$,” not “the best length among the first $i$ elements.” Why such an odd subproblem?

So that the transition knows the last element and can check that the new number is larger So that the table can be filled from left to right So that the table takes less memory

Of the best subsequence among the first $i$ elements we know only the length, and to attach a new number to it we need to know what it ends with. The subproblem “ending at $i$” stores that. When a transition won’t come out, refining the subproblem often helps.

Tasks

Five tasks, from a warm-up to one with a catch. In each, first answer the recipe’s five questions, then write the code. The tests give large inputs on which brute force and recursion without memory run out of time.

Write stairs(n, steps, broken): the number of ways to climb from the ground (step 0) to step n when one move may go up by any number of steps from the list steps and the steps in the set broken must not be stepped on. The order of moves matters: 1 + 2 and 2 + 1 are different ways. If n itself is rotten, there are no ways; for n = 0 there is one way: stay where you are. Staircases have up to ten thousand steps, and the answer is a big integer.

Take stairs from the chapter. What changes if step k is rotten? There is no way to reach it, so ways[k] = 0, and further along the table that zero does its job by itself.

The last move onto step k could be any s from steps with s <= k. Add up ways[k - s] over all such moves.

If broken comes as a list, checking k in broken will be slow on a long staircase; it is safer to do broken = set(broken) at the start. The time is $n$ times the number of allowed moves.

The till doesn’t hold unlimited coins: stock is a dictionary “value → how many such coins there are,” for example {10: 2, 5: 1, 2: 3, 1: 0}. Write min_coins(total, stock): a list of coins that pays exactly total, shortest possible, or None if it can’t be paid. If there are several best options, any will do. Amounts go up to 2,000, kinds of coins up to ten, coins of each kind up to a hundred.

The table best[s] from the chapter assumed unlimited coins of each kind. Here each coin is like a thing in the rucksack: it can be taken once. Break the stock into individual coins and add them one at a time.

If you go through the amounts in increasing order when adding a coin, the same coin may get into the change twice: best[s - c] may already contain it. Go through the amounts in decreasing order, from total down to c; then best[s - c] doesn’t know about the new coin yet. To recover the answer, keep the list of coins for each amount alongside, or “which coin improved it.”

The decreasing order is the same idea as the row best[i - 1] in the rucksack: when adding a new coin we rely on the table without it. The lists used get copied, which is extra work; it is cheaper to store only the last coin and counters for each amount, but at these sizes the simple way is enough. The time is the amount times the total number of coins: up to two million steps.

Add a fourth edit to Levenshtein distance, the swap of two neighboring letters that Damerau proposed: “teh” → “the” is one edit, not two. Write damerau(a, b). Swapped letters are not touched again: the rule is that if the last two letters of the beginning of a equal the last two letters of the beginning of b in reverse order, a fourth option joins the three in the transition: $d(i-2, j-2) + 1$. Strings are up to a thousand characters long.

Take a table d of size $(m + 1) \times (n + 1)$ with edges d[i][0] = i and d[0][j] = j and fill it as in the chapter. Check the new option only when i >= 2 and j >= 2.

The swap condition in terms of indices: a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]. Two rows of the table aren’t enough here: the transition looks two rows back, so it is simpler to keep the whole table.

This is the restricted Damerau–Levenshtein distance (also known as the optimal string alignment distance): a swapped pair is not edited again. Because of this restriction it doesn’t always satisfy the triangle inequality: from “ca” to “abc” it counts three edits, although going through “ac” two are enough. The full version without the restriction is more complicated; for spell checking this one is usually enough.

Write lcs(a, b), which returns the longest common subsequence of two strings itself: a string, not its length. If there are several, any will do. The tests check that the answer is a subsequence of both strings and that no longer one exists. Strings are up to fifteen hundred characters long.

Fill the table of lengths L as in the chapter’s diff program. Then walk back from the corner (m, n): if the letters match, take the letter and step diagonally; otherwise step toward the larger number.

Walking back collects the letters from the end. Put them in a list and reverse it at the end rather than prepending them to a string: that is quadratic work.

Stepping toward the larger number doesn’t lose the answer: if the letters differ, by the transition $L(i, j)$ equals the larger of the neighbors, and an optimal subsequence lives in the subproblem that value came from.

Write loot(items, capacity): items is a list of triples (name, weight, price) with non-negative integer weights and prices and distinct names. The function returns the list of names of the things to take so that the total weight doesn’t exceed capacity and the total price is as large as possible. If there are several best sets, any will do. There are up to a hundred things and the capacity is up to ten thousand.

The table best[i][w] is the best haul from the first i things with capacity w, as in the chapter. A hundred things and ten thousand kilograms make a million cells, which is manageable.

Recovery: go through the things from the end. If best[i][w] != best[i - 1][w], thing i was taken: subtract its weight from w. Weightless things don’t break this method: if such a thing is worth anything, the answer changes because of it.

prev and row are short names for two rows of the table: that way the inner loop does less indexing. If only the price is needed, a single row walked in decreasing order of weight is enough (the same technique as in the till with empty slots). But then the set can no longer be recovered.

What next

The spelling checker and the comparison of versions are built from the same parts. Back to the till one last time. The table finds the shortest change for any amount and any set of coins, but to do so it goes through every amount from zero up and every coin for each. A cashier at a till fills in no tables: the largest coin that fits goes into the change, then again the largest—and with American coins this somehow always ends with the fewest coins. A step that is best right now, with no thought for the future, is called greedy. When greed leads to the best answer and when it leads into a dead end with no way out is the subject of the next chapter, where greed brings electricity to the villages of Moravia.