Index Ai Academy
Phase 7 · Data structures & algorithms

Dynamic programming in depth

A method in five questions: state, choices, recurrence, base case and order. Coins where greedy fails, rebuilding the solution, packing a token budget, the likeliest path behind noisy readings, and what it costs.

About 45 minutes · A free account opens the whole lesson.
Already have an account? Sign in to open this lesson

What it covers6

Why it matters

The lesson on algorithms showed memoization and one dynamic program, edit distance. That is enough to recognize the idea and not enough to use it on a problem nobody has solved for you. This lesson teaches the method: five questions that turn "try every possibility" into a table you can fill in. It matters well beyond coding interviews. Word error rate, the alignment inside a speech recognizer, the value of a state in reinforcement learning, and choosing which passages fit in a prompt are all dynamic programs.

What you'll be able to do

  • Design a dynamic program from five questions: state, choices, recurrence, base case and order
  • Fill a table by hand and walk back along recorded choices to the answer itself
  • Plot calls against size for plain recursion and a memo, and read the growth
  • Pack a prompt to a token budget, and decode a likeliest path, with a table
Quick check
A guess before you start. A country has coins worth 1, 3 and 4. What is the fewest coins that make exactly 6?
  1. 2 coins
  2. 4 coins
  3. 3 coins
  4. 6 coins
Show the answer

2 coins

Two coins of 3. The natural method, taking the biggest coin that fits, starts with a 4 and is then forced to finish with two 1s: three coins. A rule that takes the best-looking step each time is called greedy, and here it is wrong. This lesson is about what to do when greedy can't be trusted.

The idea: Five questions that turn recursion into a table

This part rests on Searching, sorting and dynamic programming, where memoization and edit distance showed a recursive function answered from a table, and on Sequences and Σ, where a total was built term by term. Start with a rule that sounds right and is wrong.

A sensible rule that gives the wrong answer

With real coins, taking the biggest one that fits always gives the fewest coins. That is a property of the coin values, and it isn't a law. With coins of 1, 3 and 4, the rule fails.

The safe alternative is to try everything. Whatever the best answer is, it has a last coin. If that coin is a 3, the rest is the best way to make the amount minus 3. So try each coin as the last one, solve the smaller amount, and keep the best. That is a recursive function of three lines.

COINS = [1, 3, 4]

def greedy(amount):
    """Take the biggest coin that fits, again and again."""
    used = []
    for coin in sorted(COINS, reverse=True):
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used

calls = 0

def fewest(amount):
    """Try every coin as the last one, and keep the best. Correct, and very slow."""
    global calls
    calls += 1
    if amount == 0:
        return 0
    return 1 + min(fewest(amount - coin) for coin in COINS if coin <= amount)

for amount in (6, 10, 14):
    print("amount", str(amount).rjust(2), "| greedy uses", greedy(amount), "=",
          len(greedy(amount)), "coins | the fewest possible:", fewest(amount))

print()
for amount in (10, 20, 25):
    calls = 0
    fewest(amount)
    print("amount", amount, "| calls made:", format(calls, ","))
It runs right here in your browser, with nothing to install.

For 6, 10 and 14, greedy uses one coin more than necessary each time. The recursive function gets all three right.

The second table is the catch. To work out the answer for 10, the function calls itself 168 times. For 20 it takes 20,736 calls, and for 25, 229,970. Every extra unit multiplies the work by about one and a half. At that rate an amount of 100 would take longer than anyone would wait.

The waste is easy to see once you look for it. Making 25 means making 24, 22 and 21. Making 24 means making 23, 21 and 20. The answer for 21 has now been asked for twice, and each time it is worked out from nothing, all the way down. There are only 26 different amounts between 0 and 25. The function solves the same 26 problems hundreds of thousands of times.

Quick check
From the lesson on searching and sorting: memoization makes a slow recursive function fast. What does it give up in exchange?
  1. Accuracy, since stored answers are rounded
  2. Readability, since the function must be rewritten as a loop
  3. Nothing: it is faster at no cost
  4. Memory, to store each answer it has worked out
Show the answer

Memory, to store each answer it has worked out

Memoization keeps a note of every answer the first time it is computed, and returns the note on later calls. The price is the memory for those notes. For the coin problem that is one number for each amount, which is a very good trade against hundreds of thousands of repeated calls.

Five questions, and a table

Dynamic programming is the cure, and it comes down to answering five questions about a problem.

  1. What is a state? The smallest description of a subproblem. Here: the amount still to make.
  2. What are the choices at a state? Here: which coin to use.
  3. What is the recurrence? The rule that gives a state's answer from smaller states: fewest(a) = 1 + the smallest of fewest(a − coin), over the coins that fit.
  4. What is the base case? fewest(0) = 0.
  5. In what order are states needed? Smaller amounts before larger ones.

With those answered there are two ways to write the code, and both appear below. Top-down: keep the recursion and add a memo. Bottom-up: make a list, and fill it in the order from question 5, with no recursion at all.

COINS = [1, 3, 4]

calls, memo = 0, {}

def fewest(amount):
    """The same recursion, with a note of every answer already worked out."""
    global calls
    if amount in memo:
        return memo[amount]
    calls += 1
    memo[amount] = 0 if amount == 0 else 1 + min(
        fewest(amount - coin) for coin in COINS if coin <= amount)
    return memo[amount]

print("top-down, with a memo: amount 25 needs", fewest(25),
      "coins | calls that did any work:", calls)

def table(coins, amount):
    """Bottom-up: fill in the answers from 0 upward,
    so each one only needs answers already in the list."""
    best = [0] + [None] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] is not None and (
                    best[a] is None or best[a - coin] + 1 < best[a]):
                best[a] = best[a - coin] + 1
    return best

best = table(COINS, 14)
print()
print("amount:", " ".join(str(a).rjust(2) for a in range(15)))
print("coins: ", " ".join(str(b).rjust(2) for b in best))
print("with coins of 5 and 7 only: amount 12 needs", table([5, 7], 12)[12],
      "| amount 11:", table([5, 7], 11)[11])

With a memo, the amount of 25 takes 26 calls that do any work: one for each amount from 0 to 25. It took 229,970 without.

The bottom-up table shows every answer at once. Amount 6 needs 2 coins. Amount 5 needs 2 as well, a 4 and a 1. To fill in one entry the code looks back 1, 3 and 4 places, takes the smallest value it finds there, and adds one.

The last line covers a case worth planning for. With coins of 5 and 7, the amount 12 needs 2 coins, and 11 can't be made at all. The table holds None there, and the code skips states that are impossible.

Quick check
The table for coins of 1, 3 and 4 is filled in up to amount 4. What does this print: the entry for amount 5?
best = [0, 1, 2, 1, 1]          # the fewest coins for amounts 0 to 4
print(1 + min(best[5 - 1], best[5 - 3], best[5 - 4]))
  1. 3
  2. 1
  3. 5
  4. 2
Show the answer

2

The last coin is a 1, a 3 or a 4, leaving 4, 2 or 1 to make. Those need 1, 2 and 1 coins. The smallest is 1, and one more coin makes 2: a 4 and a 1, or a 1 and a 4. The new entry needed only three lookups, whatever it took to compute the earlier ones.

Try it now

Each amount reads the entries 1, 3 and 4 places back. Smaller amounts are filled first, so the answers it needs are always there.

In your own words
What are the five questions, and why does the state need to be as small as possible?

Write a sentence or two, then compare it with a good answer in the lesson.

In Python: Memos, tables and the walk back

Part 1 gave the method. Now write the code, plot what the memo saves, and recover the answer itself.

Drill

Fewest coins, bottom-up

Write fewest_coins(coins, amount): the fewest coins from coins (each usable any number of times) that add up to exactly amount, or None if it can't be made. Fill a list from 0 up to amount. Don't use recursion: the tests include an amount of 20,000.

def fewest_coins(coins, amount):
    return None


print(fewest_coins([1, 3, 4], 6), fewest_coins([5, 7], 11))
In the lesson, your code is checked as you write it.

Plot the saving

The cell below counts the calls plain recursion makes for the fewest-coins problem against the calls a memo makes, for amounts 5 to 20. The counts are exact, so the lines show growth cleanly: plain recursion curves up, the memo is a near-straight line.

from academy import measure

COINS = [1, 3, 4]

def plain_calls(amount):
    calls = 0
    def fewest(a):
        nonlocal calls
        calls += 1
        if a == 0:
            return 0
        return 1 + min(fewest(a - c) for c in COINS if c <= a)
    fewest(amount)
    return calls

def memo_calls(amount):
    calls, memo = 0, {}
    def fewest(a):
        nonlocal calls
        if a in memo:
            return memo[a]
        calls += 1
        memo[a] = 0 if a == 0 else 1 + min(fewest(a - c) for c in COINS if c <= a)
        return memo[a]
    fewest(amount)
    return calls

measure({"plain": plain_calls, "memo": memo_calls}, [5, 8, 11, 14, 17, 20],
        counts="comparisons", xlabel="amount")
Quick check
Look at the plot. When the amount grows from 14 to 17, what happens to the memo's calls and to plain recursion's?
  1. Both counts grow by the same amount, since the amount grew by 3
  2. The memo's calls multiply, while plain recursion's stay put
  3. Neither count changes, because the memo already holds the answers
  4. The memo's calls grow by about 3; plain recursion's multiply
Show the answer

The memo's calls grow by about 3; plain recursion's multiply

The memo does work once per amount, so three more amounts means three more calls. Plain recursion redoes the same subproblems along many routes, so its count multiplies.

The answer itself, not just its size

The table says that 14 takes 4 coins. It doesn't say which 4. Usually that is the part you wanted.

The fix is small and it works for every dynamic program. Whenever a state's best answer is found, also record which choice produced it. When the table is full, start at the final state and walk backward, following the recorded choices.

COINS = [1, 3, 4]

def table(coins, amount):
    best, last = [0] + [None] * amount, [None] * (amount + 1)
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] is not None and (
                    best[a] is None or best[a - coin] + 1 < best[a]):
                # also note WHICH coin gave the best answer
                best[a], last[a] = best[a - coin] + 1, coin
    return best, last

def rebuild(last, amount):
    """Walk back through the notes: take the recorded coin,
    move to the smaller amount, repeat."""
    coins = []
    while amount > 0:
        coins.append(last[amount])
        amount -= last[amount]
    return coins

best, last = table(COINS, 14)
print("amount:   ", " ".join(str(a).rjust(2) for a in range(15)))
print("fewest:   ", " ".join(str(b).rjust(2) for b in best))
print("last coin:", " ".join(str(c if c else "-").rjust(2) for c in last))
print()
for amount in (6, 10, 14):
    print("amount", str(amount).rjust(2), "->", rebuild(last, amount))

The new row, last coin, holds the coin that gave each amount its best answer. For 14 it is a 3.

To rebuild the coins for 14: the note says 3, so take a 3 and move to 11. The note at 11 says 3, so take another and move to 8. The note at 8 says 4, which leads to 4, and the note there says 4, which leads to 0. The coins are 3, 3, 4 and 4.

The walk back takes one step for each coin in the answer. All the searching was done while the table was filled, and one extra list was enough to keep its result.

There can be several equally good answers, such as 4 + 4 + 3 + 3 in another order, or 4 + 1 against 1 + 4. The walk returns one of them: whichever the code happened to record. If you need a particular one, say the earliest or the one with the fewest distinct coins, that preference has to be built into the comparison that fills the table.

Quick check
A dynamic program fills a table of best scores. What else must it keep, to report the best solution and not only its score?
  1. Every score that was considered and rejected
  2. The choice that gave each state its best score
  3. The order in which the states were filled
  4. A full copy of the best solution at every state
Show the answer

The choice that gave each state its best score

One recorded choice for each state is enough. From the final state, each recorded choice leads to the earlier state it came from, and following them back spells out the whole solution. Storing a complete solution at every state would also work, and would cost far more memory.

Drill

The cheapest path across a grid

Write cheapest_path(grid). grid is a list of rows of costs. Start at the top-left cell, move only right or down, and finish at the bottom-right. Return the lowest possible total of the cells visited, including the first and the last. The state is a cell, and the recurrence is: its cost plus the cheaper of the totals for the cell above and the cell to the left. Return 0 for an empty grid.

def cheapest_path(grid):
    return 0


print(cheapest_path([[1, 9, 1], [1, 9, 1], [1, 1, 1]]))
In the lesson, your code is checked as you write it.
In your own words
Why is it enough to store one choice per state, and not a whole solution for each state?

Write a sentence or two, then compare it with a good answer in the lesson.

In AI and ML engineering: Packing a prompt and decoding a path

The map shows where cost lives. Two of its steps are dynamic programs: choosing which passages fit a prompt, and decoding the likeliest sequence.

A state with two parts: packing a context window

Here is a problem from a retrieval system. A search step has found seven passages for a question. Each has a length in tokens and a relevance score, and there are 800 tokens of room left in the prompt. Which passages should go in, to carry the most total relevance?

Two greedy rules suggest themselves: highest score first, and best score for each token first. For the dynamic program, ask the five questions again.

  • State: which passages have been decided, and how much room is left. Two numbers: (i, b).
  • Choices: leave passage i out, or put it in.
  • Recurrence: best(i, b) is the larger of best(i − 1, b), and best(i − 1, b − cost) + score.
  • Base case: with no passages, the best score is 0.
  • Order: passage by passage.
# Passages a search step found for one question:
# (name, length in tokens, how relevant it scored).
CHUNKS = [("pricing table", 520, 9.0), ("refund policy", 300, 6.0),
          ("shipping times", 280, 5.5), ("warranty", 260, 5.0),
          ("store hours", 90, 1.5), ("careers page", 400, 1.0),
          ("returns form", 230, 4.4)]
BUDGET = 800                                    # tokens of room left in the prompt

def pack(chunks, budget, step=10):
    """best[i][b]: the highest total score using only the first i chunks,
    with b units of room (1 unit = `step` tokens)."""
    n, room = len(chunks), budget // step
    best = [[0.0] * (room + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        cost, score = chunks[i - 1][1] // step, chunks[i - 1][2]
        for b in range(room + 1):
            # choice 1: leave chunk i out
            best[i][b] = best[i - 1][b]
            if cost <= b and best[i - 1][b - cost] + score > best[i][b]:
                # choice 2: put it in, with less room for the rest
                best[i][b] = best[i - 1][b - cost] + score
    chosen, b = [], room
    # walk back: was chunk i put in?
    for i in range(n, 0, -1):
        if best[i][b] != best[i - 1][b]:
            chosen.append(i - 1)
            b -= chunks[i - 1][1] // step
    return chosen[::-1], (n + 1) * (room + 1)

def greedy(order):
    """Go through the chunks in the given order, taking each one that still fits."""
    room, chosen = BUDGET, []
    for i in order:
        if CHUNKS[i][1] <= room:
            chosen.append(i)
            room -= CHUNKS[i][1]
    return sorted(chosen)

def show(name, chosen):
    print(name.ljust(27), "| tokens", sum(CHUNKS[i][1] for i in chosen),
          "| total score", round(sum(CHUNKS[i][2] for i in chosen), 1),
          "|", ", ".join(CHUNKS[i][0] for i in chosen))

everything = range(len(CHUNKS))
show("highest score first", greedy(sorted(everything, key=lambda i: -CHUNKS[i][2])))
show("best score per token first",
     greedy(sorted(everything, key=lambda i: -CHUNKS[i][2] / CHUNKS[i][1])))
chosen, cells = pack(CHUNKS, BUDGET)
show("dynamic programming", chosen)
print()
print("cells in the table:", cells, "| possible sets of 7 chunks:", 2 ** len(CHUNKS))

Highest score first takes the pricing table, which uses 520 tokens, and has room for one more passage: a total of 14.5. Best score per token first does worse, 13.0, and leaves 130 tokens unused. The dynamic program finds a set neither rule considered: three medium passages, for 15.4.

Greedy rules go wrong here for the same reason as with the coins. An early choice that looks good uses up room that a better combination needed.

The walk back is in the last lines of pack. From the final cell, it asks at each passage whether the score changed when that passage became available. If it did, the passage was put in.

The last line is a fair warning. The table has 648 cells, and seven passages have only 128 possible sets, so trying them all would have been less work. The next part shows where that changes.

Quick check
The packing table has one row for each count of passages considered, from 0 to 7, and one column for each amount of room, from 0 to 800 tokens in units of 10. What does this print: the cells in the table, and the number of possible sets of 7 passages?
print((7 + 1) * (800 // 10 + 1), 2 ** 7)
  1. 560 14
  2. 648 49
  3. 648 128
  4. 5607 128
Show the answer

648 128

There are 8 rows and 81 columns: 648 cells. Each passage is either in or out, so 7 passages have 2⁷ = 128 possible sets. For a problem this small, brute force is cheaper. The table's size grows in step with the number of passages, while the number of sets doubles with each one.

What it costs, and when it doesn't fit

The cost of a dynamic program can be read from the five questions: the number of states, times the choices at each. Memory is the number of states.

def coins_table(coins, amount):
    best = [0] + [None] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] is not None and (
                    best[a] is None or best[a - coin] + 1 < best[a]):
                best[a] = best[a - coin] + 1
    return best

print("coins: states = amount + 1, choices at each = number of coins")
for amount in (1000, 100000):
    answer = coins_table([1, 3, 4], amount)[amount]
    print("   amount", format(amount, ",").rjust(7),
          "| steps of work:", format((amount + 1) * 3, ",").rjust(7),
          "| answer:", format(answer, ","), "coins")

print()
print("packing: states = (chunks + 1) x (units of room + 1), 2 choices at each")
print("chunks | room    | 1 unit =   | cells in the table | sets to try by brute force")
for chunks, budget, step in ((7, 800, 10), (40, 800, 10),
                             (40, 8000, 10), (40, 8000, 1)):
    unit = str(step) + (" token" if step == 1 else " tokens")
    cells = (chunks + 1) * (budget // step + 1)
    print(str(chunks).rjust(6), "|", format(budget, ",").rjust(7), "|", unit.ljust(10),
          "|", format(cells, ",").rjust(18), "|", format(2 ** chunks, ","))

For the coins, an amount of 100,000 takes about 300,000 steps. Plain recursion could not finish an amount of 100.

For packing, the comparison with brute force turns around quickly. With 40 passages there are 3,321 cells and more than a trillion possible sets.

The last two rows show the table's weakness. Its width is the size of the budget, counted in whatever unit you choose. With 8,000 tokens of room counted one token at a time, the table has 328,041 cells, a hundred times the number at 10 tokens a unit. A dynamic program over a quantity grows with the size of the number. Rounding costs to coarser units is the usual remedy, at a small cost in exactness.

Three conditions decide whether the method fits at all.

  • Subproblems overlap. If none is ever asked for twice, there is nothing to save.
  • Best answers are built from best answers. The best way to make 14 contains a best way to make 11.
  • The state is small. For the shortest route through 30 cities, visiting each once, the state must say which cities have been visited, and there are over a billion such sets.

One practical note: Python stops at about a thousand nested calls, so large tables are filled bottom-up, not by recursion.

Quick check
Which of these problems is a poor fit for dynamic programming?
  1. The most valuable set of items within a weight limit
  2. The fewest edits that turn one word into another
  3. The fewest coins that make a given amount
  4. The shortest route that visits each of 30 cities once
Show the answer

The shortest route that visits each of 30 cities once

For the route, a subproblem has to record which cities have already been visited, and 30 cities have over a billion subsets, so the table is too large to fill. The other three have small states: two positions in the words, an amount, or a count of items and the room left.

A cached recursion over a vocabulary

Tokenizing a word into the fewest pieces from a vocabulary is a dynamic program: the state is how much of the word is left, and the choices are the vocabulary pieces it starts with. functools.cache is the top-down table, one line.

from functools import cache

VOCAB = {"un", "break", "able", "unbreak", "a", "b", "e", "k", "l", "n", "r", "u"}

@cache
def fewest_tokens(text):
    if not text:
        return 0
    options = [1 + fewest_tokens(text[len(t):])
               for t in VOCAB if text.startswith(t)]
    return min(options)

print(fewest_tokens("unbreakable"))
print(fewest_tokens.cache_info().misses, "distinct suffixes worked out")

Real tokenizers use a different method (byte pair merges), but this table is the idea behind choosing the cheapest way to cover a text. Beam search and constrained decoding uses the same table-and-walk-back shape to pick the likeliest sequence of words.

Worked example

Worked example: the likeliest story behind noisy readings

A classic dynamic program in machine learning finds the best path through a chain of hidden states. A machine is either ok or failing, and it rarely switches. A sensor reads low or high each minute, and is often wrong. From 40 readings, what most likely happened? The state is (minute, condition), the choices are the two conditions a minute earlier, and the score is a log probability. It is known as the Viterbi algorithm.

import math, random

# A machine is "ok" or "failing". It rarely changes.
# Each minute a sensor reads "low" or "high", and it is noisy.
STATES = ("ok", "failing")
START = {"ok": 0.9, "failing": 0.1}
# chance of each next state
STAY = {"ok": {"ok": 0.95, "failing": 0.05}, "failing": {"ok": 0.10, "failing": 0.90}}
# chance of each reading
READS = {"ok": {"low": 0.8, "high": 0.2}, "failing": {"low": 0.3, "high": 0.7}}

rng = random.Random(3)
state, truth, readings = "ok", [], []
for minute in range(40):
    if minute:
        state = "ok" if rng.random() < STAY[state]["ok"] else "failing"
    truth.append(state)
    readings.append("low" if rng.random() < READS[state]["low"] else "high")

def best_path(readings):
    """score[s]: the log chance of the likeliest history that ends in state s now.
    One pass forward, one walk back."""
    score = {s: math.log(START[s]) + math.log(READS[s][readings[0]]) for s in STATES}
    came_from = []
    for reading in readings[1:]:
        new, back = {}, {}
        for s in STATES:
            # the best state to have come from
            before = max(STATES, key=lambda p: score[p] + math.log(STAY[p][s]))
            new[s] = (score[before] + math.log(STAY[before][s])
                      + math.log(READS[s][reading]))
            back[s] = before
        score = new
        came_from.append(back)
    path = [max(STATES, key=lambda s: score[s])]
    for back in reversed(came_from):
        path.append(back[path[-1]])
    return path[::-1]

def line(items):
    return "".join("#" if item in ("failing", "high") else "." for item in items)

def judge(name, guess):
    print(name.ljust(22), line(guess),
          "| minutes right:", sum(a == b for a, b in zip(guess, truth)), "of 40",
          "| changes of mind:", sum(a != b for a, b in zip(guess, guess[1:])))

print("sensor readings       ", line(readings), "  (# is a high reading)")
print("what really happened  ", line(truth), "  (# is failing)")
judge("each reading alone", ["failing" if r == "high" else "ok" for r in readings])
judge("likeliest whole path", best_path(readings))
print("possible paths:", format(2 ** 40, ","), "| scores computed:", 2 * 40)

import matplotlib.pyplot as plt

alone = ["failing" if r == "high" else "ok" for r in readings]
guess = best_path(readings)
rows = [("sensor: high", readings, "high"), ("truth: failing", truth, "failing"),
        ("each reading alone", alone, "failing"), ("whole path", guess, "failing")]
fig, ax = plt.subplots(figsize=(7, 2.6))
for k, (name, seq, mark) in enumerate(rows):
    level = [3 - k + 0.6 * (x == mark) for x in seq]
    ax.step(range(40), level, where="mid", label=name)
ax.set_yticks([])
ax.set_xlabel("minute")
ax.set_title("Readings, the truth and two ways to guess it")
ax.legend(loc="upper left", fontsize=7, ncol=2)
In the lesson you can change this and run it.

The second line is what really happened. Counting minutes from 0, the machine began failing at minute 27, recovered for one minute, failed again, and was back to normal for the last two. Judging each reading alone gets 30 of 40 minutes right and changes its mind 16 times, raising the alarm at minutes 5, 6, 13, 18 and 20, when nothing was wrong. The dynamic program gets 36 of 40 right and changes its mind once. It is not smoothing by a rule of thumb. For each minute and each condition it keeps the score of the likeliest history ending there, built from the two scores a minute earlier, and a recorded choice lets it walk back from the end, as in the coin problem. Two scores a minute for 40 minutes is 80 numbers, in place of a search through over a trillion possible paths. Its answer is the likeliest path under the model's assumptions, which is not always the truth: it reports the failure one minute early, and misses both the brief recovery and the return to normal at the end, since a machine that rarely switches is unlikely to have done so four times. With other random runs, a short failure that produced few high readings can be missed completely.

Quick check
Judging each sensor reading alone changed its verdict 16 times in 40 minutes. The dynamic program changed once. What lets it resist a single odd reading?
  1. It averages the readings over a fixed window of minutes
  2. It was told in advance when the machine failed
  3. It scores whole histories, and a brief switch of state is unlikely
  4. It ignores any reading that differs from the one before
Show the answer

It scores whole histories, and a brief switch of state is unlikely

Each path's score includes the chance of every change of state along it. Since the machine rarely switches, a path that flips to failing for one minute and back pays for two unlikely changes, and loses to a path that treats the reading as noise. Several high readings in a row are another matter: then a real change becomes the likelier story.

Goes deeper in

In your own words
You are given an unfamiliar optimization problem. Describe how you would decide whether dynamic programming applies, and how you would write it.

Write a sentence or two, then compare it with a good answer in the lesson.

Practice what you just read

  • 8 code examples you can edit and run
  • a practice exercise that checks your code
  • a 5-question quiz
  • 12 review cards for spaced repetition

Try a quiz question

What makes plain recursion slow on a problem such as fewest coins, and what does dynamic programming change?

  1. The same subproblems are solved again and again; each is solved once and stored
  2. Recursive calls are slow in Python; a loop runs the same steps faster
  3. The recursion tries too few options; a table tries more of them
  4. The recursion uses too much memory; a table uses none

Answer it at the end of the lesson to see if you're right, and why.

Before this lesson

Keep learning

Where this lesson leads.

575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.

Phase 7 · about 48 hours of study

Software engineering

How software is built, from bits to tested, well-designed programs 59 lessons 1 free
  1. Iterators and generators FreeThe iteration protocol, yield, lazy pipelines and itertools, in small memory.45 min
  2. Context managersSetup and cleanup that always run: with, contextlib, transactions and atomic writes.35 min
  3. Closures and decoratorsFunctions that remember, wrap and extend other functions.40 min
  4. Exceptions in depthError hierarchies, chaining, notes, exception groups and warnings.40 min
  5. Pattern matchingmatch and case: literal, sequence, mapping and class patterns with guards.35 min
  6. Text, bytes and encodingsstr and bytes, UTF-8, decoding errors, normalization and base64.35 min
  7. Binary filesBytes as numbers, endianness, struct records, file signatures and checking uploads.45 min
  8. Testing your codeAutomated tests that prove code works and keep it working.45 min
  9. Testing with pytestFixtures, parametrize, mocks, temporary files and coverage.45 min
  10. Testing numeric and random codeClose enough for floats, seeds and what they fix, properties that hold for any input, a gradient check and overfit-one-batch.40 min
  11. Debugging systematicallyFind any bug with a method instead of guesswork.35 min
  12. Readable code and refactoringWrite code people can understand, and improve it safely.35 min
  13. Code style and toolsPEP 8, formatters, linters and type checkers, and how they fit together.35 min
  14. Types and data modelingType hints, dataclasses and checking data at the edges of a program.35 min
  15. Typing in depthGenerics, protocols, TypedDict, Literal and narrowing, checked by mypy.45 min
  16. Classes in depthProperties, alternative constructors, abstract base classes and tuned dataclasses.40 min
  17. Make your classes feel built inSpecial methods for printing, equality, ordering, arithmetic and containers.45 min
  18. Software designModules, interfaces and dependencies that keep big programs changeable.45 min
  19. LoggingLoggers, levels, handlers and configuration, without leaking secrets.40 min
  20. How computers run codeBits, memory, the processor, and what really happens when Python runs.40 min
  21. Arrays in memoryBuffers, dtypes, shapes and strides: why a transpose is free, and which operations copy.40 min
  22. Algorithm complexityCount the work code does, and see why some programs stop scaling.40 min
  23. Concurrency and asyncDo many things at once: processes, threads and the event loop.45 min
  24. Performance and profilingMeasure before you optimize, then fix the part that matters.45 min
  25. Profiling numeric code and a training loopWhere a training step spends its time, Amdahl's rule by hand, and cProfile on a loop with a slow batch function.40 min
  26. Reading C, C++, CUDA and RustPointers and loops in C, references and templates in C++, one-thread-per-element CUDA kernels, and Rust's Option, Result and ownership.30 min
  27. Core data structuresArrays, linked lists, stacks, queues and the hash table behind every dict.45 min
  28. Heaps and priority queuesA list read as a tree: the best k of a million without sorting, and where top-k hides in AI work.35 min
  29. Recursion, trees and graphsFunctions that call themselves, and the shapes most real data takes.45 min
  30. Searching, sorting and dynamic programmingThe classic algorithms, and the ideas behind them.45 min
  31. Dynamic programming in depthA method in five questions: state, choices, recurrence, base case and order. Coins where greedy fails, rebuilding the solution, packing a token budget, the likeliest path behind noisy readings, and what it costs.45 min
  32. Binary search trees and traversalsInsert, search and delete in a sorted tree, walk it four ways, and see why balance and B-trees matter.45 min
  33. Patterns for coding problemsTwo pointers, counting with dictionaries, prefix sums and sliding windows: O(n) answers to classic problems.45 min
  34. Project: a spell checker, three waysA sorted list, a hash set and a trie, measured for speed and memory, with suggestions.45 min
  35. Searching for solutionsBacktracking with pruning, Dijkstra's algorithm and A*, ending with an optimal sliding-puzzle solver.45 min
  36. Project: an unbeatable game opponentGame state and rules, minimax with a cache, and an exhaustive test that proves it never loses.45 min
  37. Databases and SQLStore, query and join data with the language every database speaks.40 min
  38. SQL for analysisSubqueries, CASE, common table expressions, outer joins and window functions on real order data.45 min
  39. Designing a databaseFrom one big table to related tables: keys, constraints, many-to-many and a loader that is safe to rerun.40 min
  40. Databases with an ORMSQLAlchemy models, sessions, relationships, transactions and the N+1 problem.45 min
  41. Changing a database safelyNumbered migrations in transactions, required columns and backfills, and expand-and-contract changes.40 min
  42. Secure codingInjection, escaping, secrets and passwords: the mistakes attackers look for.40 min
  43. Projects, packaging and CILay out a real project, pin its dependencies and test it on every push.35 min
  44. Config files: YAML and TOMLWrite YAML and TOML that parse as you meant, dodge the type traps, and validate what you load.25 min
  45. Command-line programsargparse subcommands, stdin, exit codes and testable main functions.40 min
  46. Packaging your codepyproject.toml, the src layout, versions, entry points and wheels.45 min
  47. Pipes and text tools in the shellgrep, wc, sort, uniq, head and cut, chained with pipes to answer questions about logs and data.25 min
  48. JSON on the command line: curl and jqCall APIs with curl, fail on HTTP errors, and pull values out of JSON with jq paths and select.25 min
  49. Shell scripts that fail safelyTurn commands into scripts with variables, set -euo pipefail and clear exit codes, and know when to switch to Python.25 min
  50. Reading and writing XMLElementTree, attributes and text, namespaces, building XML safely, and untrusted input.35 min
  51. Project: a word-guessing gamePlan a game with a flowchart, then build it from tested functions and one input loop.40 min
  52. Project: a card game of 21Turn written rules into functions, and make randomness testable.40 min
  53. Project: a drinks kioskA program with state and commands, built with functions, then refactored into classes.45 min
  54. Project: a flashcard trainerCards from a file, review boxes, and progress saved between runs.45 min
  55. Project: a price-watch alert botAn API client, alert rules, digest emails and a state file, so reruns never repeat.45 min
  56. Project: Pack Train, an arcade gameA grid game on the turtle canvas: game state as classes, a timer loop, key handlers and a saved best score.45 min
  57. Project: a private password-breach checkHash locally, send five characters, match locally: k-anonymity, safe logging and failure handling.40 min
  58. Capstone: a command-line appDesign, build and test a complete program with a database.45 min
  59. Capstone: ship a small model libraryA typed, tested and profiled package with a train and an eval command, a YAML config, logging and a wheel.45 min

Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write