Skip to content
LumenaryAcademy
Algorithms 75 min

Dynamic programming

Solve each subproblem once and remember the answer — and learn the real skill, which is deciding what the subproblems should be.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

IntuitionH

Fibonacci, the slow way and the fast way

The Fibonacci numbers satisfy F0=0F_0 = 0, F1=1F_1 = 1 and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}. The definition is a recursive program, and a terrible one:

python
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 φn\varphi^n with φ≈1.618\varphi \approx 1.618: about 102010^{20} 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.

DefinitionsH

Definitions

Definition— state and recurrence

A state is a description of a subproblem, typically a few integers such as "the first ii items and capacity ww". 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.

ExplanationH

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)
Codethe recurrence, almost verbatimneeds an explicit evaluation order
States computedonly those actually reachableall states in the table
Recursion depthcan hit Python's limit (about 1000)none
Overhead per statea function call and a dict lookupan array access
Saving memoryhardoften 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.

python
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] + "...")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Coin change, done right

The previous lesson showed greedy change-making failing for coins such as 1,3,41, 3, 4. Dynamic programming always succeeds. Let best[a] be the fewest coins that sum to aa. The last coin used is some c≤ac \le a, and the rest must be an optimal way to pay a−ca - c (optimal substructure: if it were not, replacing it would improve the whole). So

best[0]=0,best[a]=1+min⁡c≤abest[a−c].\text{best}[0] = 0, \qquad \text{best}[a] = 1 + \min_{c \le a} \text{best}[a - c].

Fill the table for a=0,1,…,Aa = 0, 1, \ldots, A: each entry looks at kk coins, so the cost is O(kA)O(kA). To reconstruct the coins, store which coin achieved the minimum at each amount, then follow the choices back from AA. This store-the-choice pattern works for every dynamic program in this lesson.

A related question: in how many ways can amount AA 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.

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

One more observation: O(kA)O(kA) looks polynomial, but AA is a number in the input, written with about log⁡2A\log_2 A digits. Doubling the number of digits squares AA. 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.

ExplanationH

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 a=a1…ama = a_1 \ldots a_m and b=b1…bnb = b_1 \ldots b_n, and let L[i][j]L[i][j] be the LCS length of the prefixes a1…aia_1 \ldots a_i and b1…bjb_1 \ldots b_j.

Theorem— The LCS recurrence

L[i][0]=L[0][j]=0L[i][0] = L[0][j] = 0, and for i,j≥1i, j \ge 1:

L[i][j]={L[i−1][j−1]+1if ai=bj,max⁡(L[i−1][j], L[i][j−1])if ai≠bj.L[i][j] = \begin{cases} L[i-1][j-1] + 1 & \text{if } a_i = b_j, \\ \max\big(L[i-1][j],\ L[i][j-1]\big) & \text{if } a_i \ne b_j. \end{cases}

Proof

If ai≠bja_i \ne b_j, a common subsequence cannot end with both aia_i and bjb_j matched to each other, so it does not use aia_i or does not use bjb_j; it is therefore a common subsequence of (a1..i−1,b1..j)(a_{1..i-1}, b_{1..j}) or of (a1..i,b1..j−1)(a_{1..i}, b_{1..j-1}), and the best is the larger of those two. If ai=bja_i = b_j, take any longest common subsequence ss of the prefixes, and suppose its last character is matched at positions (p,q)≠(i,j)(p, q) \ne (i, j). Both p<ip < i and q<jq < j cannot hold, since then appending the match of aia_i with bjb_j would give a longer common subsequence. So exactly one of p=ip = i, q=jq = j holds, and because the last character of ss equals ai=bja_i = b_j, it can be re-matched to the pair (ai,bj)(a_i, b_j). Hence some longest ss ends with that match; removing it leaves a common subsequence of the prefixes of lengths i−1i-1 and j−1j-1, which must itself be longest. So L[i][j]=L[i−1][j−1]+1L[i][j] = L[i-1][j-1] + 1.

∎

The table has (m+1)(n+1)(m+1)(n+1) entries, each computed in O(1)O(1): O(mn)O(mn) time and space. Reconstruct by walking back from L[m][n]L[m][n]: 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 O((m+n)D)O((m+n)D) time, where DD 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.

ExplanationH

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 D[i][j]D[i][j] be the distance between the prefixes a1..ia_{1..i} and b1..jb_{1..j}. Consider the last characters. In an optimal edit, aia_i is either deleted, or bjb_j is inserted at the end, or aia_i ends up as bjb_j (free if they are equal, one substitution otherwise). So

D[i][j]=min⁡(D[i−1][j]+1,  D[i][j−1]+1,  D[i−1][j−1]+[ai≠bj]),D[i][j] = \min\big(D[i-1][j] + 1,\ \ D[i][j-1] + 1,\ \ D[i-1][j-1] + [a_i \ne b_j]\big),

with D[i][0]=iD[i][0] = i (delete everything) and D[0][j]=jD[0][j] = j (insert everything). Again O(mn)O(mn) 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.

python
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)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

The 0/1 knapsack

A rural clinic has a budget of WW and a list of items (a refrigerator for vaccines, a solar panel, a microscope, a motorbike for outreach), each with a cost wiw_i and a value viv_i. 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: K[i][c]K[i][c] = the best value achievable using only the first ii items with budget cc. Choice: item ii is either left out, or bought (if it fits), leaving budget c−wic - w_i for the first i−1i - 1 items:

K[i][c]=max⁡(K[i−1][c],  vi+K[i−1][c−wi] if wi≤c),K[0][c]=0.K[i][c] = \max\big(K[i-1][c],\ \ v_i + K[i-1][c - w_i] \text{ if } w_i \le c\big), \qquad K[0][c] = 0.

The table has (n+1)(W+1)(n+1)(W+1) entries: O(nW)O(nW) 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 K[n][W]K[n][W]: if K[i][c]≠K[i−1][c]K[i][c] \ne K[i-1][c], item ii was bought.

To save memory, keep a single row and update it for each item, iterating the budget downwards from WW to wiw_i. Downwards matters: each update reads entries for smaller budgets, which still hold the values before item ii 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.

ExplanationH

State design is the real skill

Every example so far followed the same recipe:

  1. Define the state in words, precisely: "D[i][j]D[i][j] is the edit distance between the first ii letters of aa and the first jj letters of bb."
  2. Write the recurrence by asking what the last decision is (the last coin, the last characters, the last item) and trying every option.
  3. Fix the base cases and the evaluation order: the states must form a DAG, and the table must be filled in a topological order.
  4. Count the cost: number of states times work per state.
  5. 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 i,i+1,…i, i+1, \ldots 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 ii, she needs to know only the best total up to i−1i - 1 and up to i−2i - 2; 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, O(2nn2)O(2^n n^2): exponential, but for 20 cities about 400 million steps instead of the 19!/2≈6×101619!/2 \approx 6 \times 10^{16} 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 misconceptionsH

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 WW in about log⁡2W\log_2 W bits, so O(nW)O(nW) is exponential in the input size. With costs measured in cents and a budget of a billion, the table has 10910^9 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

Exercises

1. Dynamic programming

Warm-upHuman

Which of these naive recursive algorithms have overlapping subproblems, so that memoisation would save a large amount of work? Select all that apply.

Choose all that apply

2. Dynamic programming

Warm-upHuman

Using 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 5+55 + 5 is one way, and 2+1+…2 + 1 + \ldots is the same way as 1+2+…1 + 2 + \ldots.)

3. Dynamic programming

CoreHuman

What is the length of a longest common subsequence of ALGORITHM and LOGARITHM?

4. Dynamic programming

CoreHuman

The 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

CoreComputational

A 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 O(n⋅budget)O(n \cdot \text{budget}) dynamic program from the lesson and reconstruct the choice from the table.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Dynamic programming

StretchComputational

Lay 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?)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Dynamic programming

CoreHuman

The knapsack dynamic program runs in O(nW)O(nW) time for nn items and budget WW. The knapsack problem is NP-hard. Why is there no contradiction?

Choose one

8. Dynamic programming

CoreHuman

To 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?

Choose one

Further reading and resources