Remember, don't recompute
Type recieve into a word processor and it suggests receive. Run git diff and it shows the fewest lines to delete and add to turn one version of a file into the next. A bioinformatician in Nairobi aligns the genome of a cassava virus against a known strain to see where they differ. TeX lays out a paragraph by choosing all its line breaks at once, so that no line is stretched too far. A database chooses in which order to join five tables, out of more than a hundred possible plans.
Each of these problems can be written as a recursion: the best answer for the whole is built from the best answers for smaller pieces. Written naively, though, the recursion re-solves the same pieces again and again, and the running time explodes exponentially. Dynamic programming is the remedy: solve each distinct subproblem once, store its answer, and look it up whenever it is needed again. The idea is simple, and the payoff is often the difference between centuries and milliseconds.
Where greedy algorithms (previous lesson) commit to one choice and hope, dynamic programming tries every choice for every subproblem, and gets away with it because there are few distinct subproblems. The hard part, and the real skill, is choosing which subproblems.
Fibonacci, the slow way and the fast way
The Fibonacci numbers satisfy , and . The definition is a recursive program, and a terrible one:
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again, and fib(2) is computed three times. The number of calls satisfies the same recurrence as the Fibonacci numbers themselves, so it grows like with : about calls for fib(100) (see recurrences). Yet there are only 101 different questions, fib(0) to fib(100). The recursion is slow because its subproblems overlap.
Picture the distinct subproblems as vertices of a graph, with an edge from each subproblem to the ones it needs. For Fibonacci it is a simple chain; for the problems below it is a grid. This graph is always a DAG (a subproblem cannot depend on itself), and dynamic programming is nothing more than evaluating it: either top-down, recursing but remembering every answer, or bottom-up, filling in answers in a topological order (from Graphs) so that everything a subproblem needs is ready before it.
The name is historical rather than descriptive. Richard Bellman chose it in the early 1950s while working on multistage decision problems; he later recalled that "dynamic" sounded impressive and was a word nobody could use in a bad sense, which helped at a time when the very word research was unwelcome to the officials who paid for his work. "Programming" meant planning, as in a television programme, not writing code.
Definitions
Definition— state and recurrence
A state is a description of a subproblem, typically a few integers such as "the first items and capacity ". A recurrence expresses the answer for a state in terms of answers for smaller states; base cases give the answers for the smallest states directly.
Definition— overlapping subproblems
A recursive solution has overlapping subproblems when the same states are reached by many different paths of the recursion, so that the number of distinct states is much smaller than the number of recursive calls.
Definition— optimal substructure
An optimisation problem has optimal substructure when an optimal solution consists of an optimal choice plus optimal solutions to the subproblems that choice leaves behind.
Definition— memoisation and tabulation
Memoisation (top-down) keeps the recursive code and stores each answer in a table the first time it is computed. Tabulation (bottom-up) allocates the table explicitly and fills it in an order in which every state's dependencies come first.
Memoisation and tabulation in Python
Python makes memoisation a one-line change. functools.cache (Python 3.9 and later; lru_cache(maxsize=None) before that) wraps a function with a dictionary from arguments to results. The arguments must therefore be hashable: numbers, strings and tuples are fine, lists are not (see Hash tables).
The two styles have complementary strengths.
| Memoisation (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| Code | the recurrence, almost verbatim | needs an explicit evaluation order |
| States computed | only those actually reachable | all states in the table |
| Recursion depth | can hit Python's limit (about 1000) | none |
| Overhead per state | a function call and a dict lookup | an array access |
| Saving memory | hard | often easy: keep only the last row or two |
A good working habit: write the recurrence with @cache first, because it is the clearest statement of the idea and easy to check against brute force; switch to a table when you need speed, deep recursion or less memory.
from functools import cache
import time
calls = 0
def fib_naive(n):
global calls
calls += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@cache
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
prev, cur = 0, 1 # only the last two entries of the table are needed
for _ in range(n):
prev, cur = cur, prev + cur
return prev
t = time.perf_counter()
print("fib(27) =", fib_naive(27), f"with {calls:,} calls in {time.perf_counter() - t:.2f}s")
t = time.perf_counter()
print("fib(27) =", fib_memo(27), "memoised:", fib_memo.cache_info().currsize, "distinct calls,",
f"{time.perf_counter() - t:.5f}s")
print("fib(300) =", fib_table(300))
fib_memo.cache_clear()
try:
fib_memo(5000) # each new n recurses one level deeper
except RecursionError:
print("fib_memo(5000): RecursionError, so use the table:", str(fib_table(5000))[:20] + "...")Coin change, done right
The previous lesson showed greedy change-making failing for coins such as . Dynamic programming always succeeds. Let best[a] be the fewest coins that sum to . The last coin used is some , and the rest must be an optimal way to pay (optimal substructure: if it were not, replacing it would improve the whole). So
Fill the table for : each entry looks at coins, so the cost is . To reconstruct the coins, store which coin achieved the minimum at each amount, then follow the choices back from . This store-the-choice pattern works for every dynamic program in this lesson.
A related question: in how many ways can amount be paid? Here the order of the loops decides what is counted. Looping over coins on the outside and amounts on the inside builds each payment with its coins in a fixed order, so each combination is counted once. Looping over amounts on the outside lets any coin come last, so different orderings of the same coins are counted separately. Both are correct answers to different questions, and confusing them is one of the most common dynamic-programming bugs.
def fewest_coins(coins, amount):
INF = float("inf")
best = [0] + [INF] * amount
last = [None] * (amount + 1) # the coin used last in an optimal payment of a
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a], last[a] = best[a - c] + 1, c
if best[amount] == INF:
return None
used, a = [], amount
while a > 0: # follow the stored choices back to 0
used.append(last[a])
a -= last[a]
return used
old_uk = [1, 3, 6, 12, 24, 30] # pence, before 1971
print("48d:", fewest_coins(old_uk, 48))
print("6 with 1, 3, 4:", fewest_coins([1, 3, 4], 6))
print("7 with 4, 6:", fewest_coins([4, 6], 7))
def ways_combinations(coins, amount):
ways = [1] + [0] * amount
for c in coins: # coins outside: each multiset counted once
for a in range(c, amount + 1):
ways[a] += ways[a - c]
return ways[amount]
def ways_orderings(coins, amount):
ways = [1] + [0] * amount
for a in range(1, amount + 1): # amounts outside: 1+2 and 2+1 both counted
ways[a] = sum(ways[a - c] for c in coins if c <= a)
return ways[amount]
print("pay 5 with 1, 2, 5:", ways_combinations([1, 2, 5], 5), "combinations,",
ways_orderings([1, 2, 5], 5), "ordered sequences")One more observation: looks polynomial, but is a number in the input, written with about digits. Doubling the number of digits squares . Running times polynomial in the numeric value rather than the input length are called pseudo-polynomial, and they come back in the knapsack problem below.
Longest common subsequence
A subsequence of a string keeps some of its characters in their original order: GTA is a subsequence of GATTACA. The longest common subsequence (LCS) of two strings measures how much they share in order, and it underlies diff tools and DNA comparison.
Let and , and let be the LCS length of the prefixes and .
Theorem— The LCS recurrence
, and for :
Proof
If , a common subsequence cannot end with both and matched to each other, so it does not use or does not use ; it is therefore a common subsequence of or of , and the best is the larger of those two. If , take any longest common subsequence of the prefixes, and suppose its last character is matched at positions . Both and cannot hold, since then appending the match of with would give a longer common subsequence. So exactly one of , holds, and because the last character of equals , it can be re-matched to the pair . Hence some longest ends with that match; removing it leaves a common subsequence of the prefixes of lengths and , which must itself be longest. So .
∎
The table has entries, each computed in : time and space. Reconstruct by walking back from : on a match, step diagonally and record the character; otherwise step towards the larger neighbour. If only the length is needed, two rows suffice, and Daniel Hirschberg (1975) showed how to recover the subsequence itself in linear space by divide and conquer.
Run on lines instead of characters, the LCS is the part of a file that did not change, and everything else is a deletion or an insertion: that is a diff. Production tools refine the idea. git diff by default uses Eugene Myers's 1986 algorithm, which finds a shortest edit script in time, where is the size of the difference, which is fast when two versions are similar; Python's difflib uses a different heuristic that produces readable but not always minimal diffs.
Edit distance
How far apart are two words? The edit distance (Levenshtein distance, after Vladimir Levenshtein, who studied it in 1965) is the fewest single-character insertions, deletions and substitutions that turn one into the other. Spell checkers rank suggestions by it, search engines tolerate typos with it, and record-linkage systems use it to recognise Mohamed and Muhammad, or Tchaikovsky and Tschaikowsky, as the same name.
Let be the distance between the prefixes and . Consider the last characters. In an optimal edit, is either deleted, or is inserted at the end, or ends up as (free if they are equal, one substitution otherwise). So
with (delete everything) and (insert everything). Again time. Robert Wagner and Michael Fischer published this table algorithm in 1974; biologists had found the same idea for protein alignment in 1970 (Saul Needleman and Christian Wunsch), with scores for matches and gaps in place of unit costs.
def lcs_table(a, b):
m, n = len(a), len(b)
L = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L
def lcs(a, b):
L, out, i, j = lcs_table(a, b), [], len(a), len(b)
while i and j: # walk back from the corner
if a[i - 1] == b[j - 1]:
out.append(a[i - 1]); i -= 1; j -= 1
elif L[i - 1][j] >= L[i][j - 1]:
i -= 1
else:
j -= 1
return out[::-1]
def diff(a, b):
"""A minimal line diff: unchanged lines are the LCS, everything else is deleted or inserted."""
L, out, i, j = lcs_table(a, b), [], len(a), len(b)
while i or j:
if i and j and a[i - 1] == b[j - 1]:
out.append(" " + a[i - 1]); i -= 1; j -= 1
elif j and (i == 0 or L[i][j - 1] >= L[i - 1][j]):
out.append("+ " + b[j - 1]); j -= 1
else:
out.append("- " + a[i - 1]); i -= 1
return out[::-1]
old = ["def area(r):", " pi = 3.14", " return pi * r * r"]
new = ["import math", "", "def area(r):", " return math.pi * r * r"]
print(*diff(old, new), sep="\n")
print("letters in common, in order:", "".join(lcs("ALGORITHM", "ALTRUISM")))
def edit_distance(a, b, show=False):
m, n = len(a), len(b)
D = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
D[i][0] = i
for j in range(n + 1):
D[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
D[i][j] = min(D[i - 1][j] + 1, # delete a[i-1]
D[i][j - 1] + 1, # insert b[j-1]
D[i - 1][j - 1] + (a[i - 1] != b[j - 1])) # keep or substitute
if show:
print(" " + "".join(f"{ch:>3}" for ch in b))
for i in range(m + 1):
print(f" {(' ' + a)[i]} " + "".join(f"{x:3}" for x in D[i]))
return D[m][n]
print("distance:", edit_distance("sitar", "guitar", show=True))
for x, y in [("Mohamed", "Muhammad"), ("Tchaikovsky", "Tschaikowsky"), ("recieve", "receive")]:
print(f"{x} -> {y}: {edit_distance(x, y)}")The 0/1 knapsack
A rural clinic has a budget of and a list of items (a refrigerator for vaccines, a solar panel, a microscope, a motorbike for outreach), each with a cost and a value . Each item is bought whole or not at all. Which items maximise the total value within the budget? Greedy by value per cost fails here, as the previous lesson showed.
State: = the best value achievable using only the first items with budget . Choice: item is either left out, or bought (if it fits), leaving budget for the first items:
The table has entries: time, pseudo-polynomial again, which is consistent with the knapsack problem being NP-hard (Hard problems): the algorithm is fast only when the budget, as a number, is small. To reconstruct the chosen items, walk back from : if , item was bought.
To save memory, keep a single row and update it for each item, iterating the budget downwards from to . Downwards matters: each update reads entries for smaller budgets, which still hold the values before item was considered, so the item is used at most once. Iterating upwards would let an item be reused, which solves the unbounded knapsack instead, the same loop-order subtlety as in coin change. You will implement the knapsack with reconstruction in the exercises.
State design is the real skill
Every example so far followed the same recipe:
- Define the state in words, precisely: " is the edit distance between the first letters of and the first letters of ."
- Write the recurrence by asking what the last decision is (the last coin, the last characters, the last item) and trying every option.
- Fix the base cases and the evaluation order: the states must form a DAG, and the table must be filled in a topological order.
- Count the cost: number of states times work per state.
- Reconstruct by remembering which option won.
Step 1 is where the thinking happens. The guiding question is: what do the remaining decisions need to know about the decisions already made? The state must contain exactly that, and nothing more. Some examples:
- Breaking a paragraph into lines. What matters for the rest of the paragraph is only where the next line starts, so the state is a single index: the cost of laying out words optimally. TeX's line-breaking algorithm (Donald Knuth and Michael Plass, 1981) is a refined version of this, and you will write a simple one in the exercises.
- Choosing non-adjacent plots. A farmer may plant on any plots along a row except two adjacent ones. To decide about plot , she needs to know only the best total up to and up to ; the state is the position.
- The travelling salesperson. To finish a tour, you need to know which cities are already visited and where you are now, but not the order in which you visited them. The state (set of visited cities, current city) gives the Held–Karp algorithm, : exponential, but for 20 cities about 400 million steps instead of the tours.
- Join order in a database. System R's optimiser (Selinger and colleagues, 1979) keeps, for each subset of tables, the cheapest plan that joins them. Modern query optimisers still use this idea for moderate numbers of tables.
When the honest answer to "what must the future know?" is "almost everything", the number of states explodes, and that is often a sign the problem is genuinely hard. Dynamic programming also appears in the Viterbi algorithm (decoding in speech recognition and mobile networks), in reinforcement learning, whose Bellman equations are dynamic programs over the states of an environment, and in nearly every algorithm that compares sequences.
Common misconceptions
Misconception
"Dynamic programming means adding a cache to a recursive function." The cache is the easy part. A cache on a function whose arguments do not capture the right state, or whose states number in the billions, does not help. The work is in defining the state and the recurrence; memoisation is one way to evaluate it.
Misconception
"O(nW) is polynomial, so the knapsack problem is easy." The input encodes in about bits, so is exponential in the input size. With costs measured in cents and a budget of a billion, the table has columns per item.
Misconception
"The order of the loops doesn't matter." It matters twice in this lesson: coins outside counts combinations while amounts outside counts orderings, and iterating a one-row knapsack upwards silently turns the 0/1 problem into the unbounded one. Always ask which table entries an update reads, and whether they are "before" or "after" the current choice.
Misconception
"Top-down is always slower than bottom-up." It has more overhead per state, but it computes only the states it actually needs. When most of the table is unreachable, memoisation can win by a wide margin.
Exercises
1. Dynamic programming
Warm-upHumanWhich of these naive recursive algorithms have overlapping subproblems, so that memoisation would save a large amount of work? Select all that apply.
2. Dynamic programming
Warm-upHumanUsing coins worth 1, 2 and 5 (as many of each as you like), in how many ways can you pay 10, if the order of the coins does not matter? (So is one way, and is the same way as .)
3. Dynamic programming
CoreHumanWhat is the length of a longest common subsequence of ALGORITHM and LOGARITHM?
4. Dynamic programming
CoreHumanThe city once written Peking in English is now written Beijing. What is the edit distance (insertions, deletions and substitutions of single letters, each costing 1) between beijing and peking?
5. Dynamic programming
CoreComputationalA rural clinic can spend at most budget (a non-negative integer) on equipment. items is a list of (name, cost, value) with positive integer costs. Each item is bought whole or not at all.
Write knapsack(items, budget) that returns (best_value, chosen), where chosen is a list of the names of the items to buy, in the order they appear in items, achieving the maximum total value within the budget. Use the dynamic program from the lesson and reconstruct the choice from the table.
6. Dynamic programming
StretchComputationalLay out a paragraph in lines of at most width characters. Words on a line are separated by single spaces, words are never split (every word fits within width), and the penalty of every line except the last is the square of its number of unused characters, (width - len(line)) ** 2. The last line is free.
Write best_breaks(words, width) that returns (total_penalty, lines) with the smallest possible total penalty, where lines is the list of line strings. The obvious greedy approach (fill each line as full as possible) is not optimal: for "the light shines in the darkness".split() and width 9 it scores 36, but 18 is possible.
Design the state yourself. (Hint: what does the rest of the paragraph need to know about the lines already laid out?)
7. Dynamic programming
CoreHumanThe knapsack dynamic program runs in time for items and budget . The knapsack problem is NP-hard. Why is there no contradiction?
8. Dynamic programming
CoreHumanTo save memory, a 0/1 knapsack keeps one row best[c] and, for each item with cost w and value v, runs
for c in range(w, budget + 1): # upwards
best[c] = max(best[c], v + best[c - w])
What does this code actually compute?
Further reading and resources
- functools.cache · Python documentation
- The String-to-String Correction Problem · Robert A. Wagner and Michael J. Fischer · 1974The dynamic program for edit distance, in its classic form.
- A linear space algorithm for computing maximal common subsequences · Daniel S. Hirschberg · 1975
- An O(ND) difference algorithm and its variations · Eugene W. Myers · 1986The algorithm behind git's default diff.
- A general method applicable to the search for similarities in the amino acid sequence of two proteins · Saul B. Needleman and Christian D. Wunsch · 1970
- Breaking paragraphs into lines · Donald E. Knuth and Michael F. Plass · 1981How TeX chooses line breaks for a whole paragraph at once.
- Access path selection in a relational database management system · Patricia Selinger and others · 1979The System R paper; its dynamic program over join orders still shapes query optimisers.
- difflib — Helpers for computing deltas · Python documentation
- Algorithms, chapter 3 (Dynamic Programming) · Jeff Erickson