Dynamic Programming

Recognizing a DP problem

Recall Fibonacci from M28: fib(n) = fib(n-1) + fib(n-2). The direct recursive version is beautiful and hopeless: fib(40) makes over 300 million calls. The reason is visible in the call tree below: fib(3) is computed again and again, in every branch that needs it. Turn on memoization in the visualizer and watch the tree collapse into a single chain.

A problem is a good fit for DP when it has both of these properties:

• Optimal substructure: an optimal answer to the whole problem is built from optimal answers to smaller subproblems. The cheapest way to reach step 10 ends with the cheapest way to reach step 9 or 8, plus one last move.
• Overlapping subproblems: the same subproblems recur many times. Merge sort has optimal substructure but its halves never overlap, so it is divide and conquer, not DP. Fibonacci's subproblems overlap massively.

Signals in a problem statement that suggest DP: "count the number of ways", "minimum/maximum cost", "is it possible to", "longest/shortest subsequence", choices made in sequence where an early choice limits later ones, and inputs small enough (n ≤ a few thousand, capacity ≤ 10⁵) that an O(n²) or O(n·W) table fits.

Remember: exponential recursion plus repeated subproblems is the fingerprint of DP. Count the distinct subproblems and the work per subproblem; their product is the DP's running time.

Top-down memoization vs bottom-up tabulation

There are two ways to make each subproblem run once.

Top-down (memoization) keeps the recursive code and caches results. In Python that is one decorator: functools.cache stores every result in a dict keyed by the arguments (which must therefore be hashable). functools.lru_cache(maxsize=N) does the same with a size bound.

Bottom-up (tabulation) fills a table from the smallest subproblems upward, in an order that guarantees every dependency is ready before it is needed. No recursion, no cache lookups, no recursion limit.

Designing the state: a five-step recipe

The hard part of DP is never the loop. It is deciding what a subproblem is. Use this recipe on every problem, and write each step down before coding.

1. Define the state in words. "dp[i] = the minimum cost to stand on step i." If you cannot say it in one sentence, the state is wrong. The state must capture everything about the past that affects the future, and nothing more.
2. Write the recurrence by considering the last decision. To stand on step i, the last move came from i-1 or i-2: dp[i] = min(dp[i-1], dp[i-2]) + cost[i].
3. Base cases: the smallest states that the recurrence cannot reduce: dp[0] = cost[0], dp[1] = cost[1].
4. Evaluation order: every state must be computed after the states it depends on. Here, increasing i.
5. Where is the answer? Often dp[n], sometimes max(dp), sometimes min(dp[n-1], dp[n-2]). Then ask: do I need the solution itself, not just its value? If so, plan for reconstruction.

The complexity falls out of the state: (number of states) × (work per state). Climbing stairs has n states and O(1) work each: O(n) time, O(n) space (O(1) with rolling variables).

Coin change: minimum coins and number of ways

Given coin denominations and an amount, two classic questions share one table shape.

Minimum coins. State: dp[a] = fewest coins that sum to a. Last decision: which coin was added last? dp[a] = 1 + min(dp[a - c] for c in coins if c <= a), with dp[0] = 0 and infinity meaning "impossible". O(amount × coins) time, O(amount) space.

Number of ways. State: ways[a] = number of multisets of coins summing to a. Here the loop order matters enormously. Put coins in the outer loop and each combination is counted once, because coins are introduced in a fixed order. Put amounts outside and you count ordered sequences (1+2 and 2+1 separately).

Remember: the loop nesting is part of the state definition. "Ways using only the first k coin types" is a different subproblem from "ways ending in any coin".

0/1 knapsack

You have items with weights and values and a bag of capacity W. Each item is taken or not (0/1). Brute force tries 2ⁿ subsets. DP state: best[i][w] = the best value using only the first i items with capacity w. Last decision: was item i taken?

best[i][w] = max(best[i-1][w],                         # skip item i
                 best[i-1][w - weight[i]] + value[i])  # take it (only if weight[i] <= w)

Why it is correct (optimal substructure): take any optimal packing of the first i items with capacity w. If it skips item i, it is an optimal packing of the first i−1 items with capacity w (otherwise a better one would improve it). If it takes item i, the rest is an optimal packing of i−1 items with capacity w − weight[i]. The max over both cases is therefore optimal.

Time and space: O(n·W). This is pseudo-polynomial: polynomial in the numeric value W, but W can be exponential in the number of digits used to write it. Knapsack is NP-hard in general; DP wins when W is modest.

Rolling array. Row i only reads row i−1, so one 1-D list suffices if you iterate w downwards: then dp[w - wt] still holds the previous row's value.

Two-string DP: LCS and edit distance

When the input is two sequences, the state is usually a pair of prefix lengths: dp[i][j] describes a[:i] versus b[:j]. The last decision looks at the last characters.

Longest common subsequence (LCS)

A subsequence keeps order but may skip elements ("ACE" is a subsequence of "ABCDE"). LCS is the backbone of diff and of version control merges.

if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1          # extend a common subsequence
else:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # drop the last char of a or of b

Edit distance (Levenshtein)

The minimum number of single-character inserts, deletes, and substitutions turning a into b. It drives "did you mean" suggestions. Base cases: turning a prefix of length i into the empty string costs i deletions, so dp[i][0] = i and dp[0][j] = j.

dp[i][j] = dp[i-1][j-1]                  if a[i-1] == b[j-1]
         = 1 + min(dp[i-1][j],           # delete a[i-1]
                   dp[i][j-1],           # insert b[j-1]
                   dp[i-1][j-1])         # substitute

Both run in O(m·n) time. LCS and edit distance need O(m·n) space if you want to reconstruct; with two rolling rows the value alone needs O(min(m, n)).

Longest increasing subsequence: O(n²) and O(n log n)

Find the length of the longest strictly increasing subsequence of a list. The classic state: dp[i] = length of the longest increasing subsequence ending at index i. Ending at a fixed position is a powerful trick: it tells the recurrence what the last element is.

dp[i] = 1 + max((dp[j] for j in range(i) if a[j] < a[i]), default=0)
answer = max(dp)        # the answer can end anywhere

That is O(n²). A cleverer state gets O(n log n): tails[k] = the smallest possible tail of an increasing subsequence of length k + 1 seen so far. tails is always sorted, so for each new value binary search (bisect_left, from M30) finds the first tail that is ≥ it and replaces it (a smaller tail is never worse), or appends if the value beats every tail.

Grid paths and word break

Grid paths. A robot moves only right or down on an m × n grid with some blocked cells. The number of paths to cell (r, c) is the sum of the paths to the cell above and the cell to the left; a blocked cell has 0. The same shape solves minimum path sum (replace + with min, add the cell cost).

Word break. Can a string be split into dictionary words? State: ok[i] = "the prefix s[:i] can be segmented". Last decision: the last word s[j:i]. ok[i] = any(ok[j] and s[j:i] in words for j in range(i)). Storing which j worked lets you rebuild the split.

Word break is O(n·L) checks where L is the longest word, each slice costing up to O(L). Limiting j to the last L positions is a standard pruning that turns O(n²) into O(n·L).

Space optimization and reconstructing solutions

Two habits separate textbook DP from production DP.

Rolling arrays

If row i only reads row i−1 (knapsack, LCS, edit distance, grid paths), keep only two rows, or one row with a careful iteration direction. That turns O(n·W) memory into O(W). Fibonacci and climbing stairs need only two variables. The cost: you lose the table you would walk backwards for reconstruction.

Reconstruction

Optimization DPs answer "how good is the best?" but users want "what is the best?". Two techniques:

• Re-derive from the table: stand at the answer cell and ask which case of the recurrence produced it (knapsack, LCS). Needs the full table.
• Store a choice pointer alongside each value (last coin, back index in word break). Costs one extra array but makes the walk trivial.

Remember: decide early whether you need the solution or only its value. That decision determines whether you can roll the array.

Practice

def min_cost_climb(cost: list[int]) -> int:
    two_back, one_back = 0, 0          # cost to arrive at steps i-2 and i-1
    for i in range(2, len(cost) + 1):
        two_back, one_back = one_back, min(one_back + cost[i - 1], two_back + cost[i - 2])
    return one_back

import math

def fewest_coins(coins: list[int], amount: int) -> int:
    dp = [0] + [math.inf] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return -1 if dp[amount] == math.inf else int(dp[amount])

def count_ways(coins: list[int], amount: int) -> int:
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

def edit_script(a: str, b: str) -> tuple[int, list[str]]:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    ops: list[str] = []
    i, j = m, n
    while i or j:
        if i and j and a[i - 1] == b[j - 1] and dp[i][j] == dp[i - 1][j - 1]:
            i, j = i - 1, j - 1
        elif i and j and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"replace {a[i - 1]!r} with {b[j - 1]!r} at {i - 1}")
            i, j = i - 1, j - 1
        elif i and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"delete {a[i - 1]!r} at {i - 1}")
            i -= 1
        else:
            ops.append(f"insert {b[j - 1]!r} at {i}")
            j -= 1
    return dp[m][n], ops[::-1]

from bisect import bisect_left

def longest_increasing(a: list[int]) -> list[int]:
    tails: list[int] = []
    tail_idx: list[int] = []
    prev = [-1] * len(a)
    for i, x in enumerate(a):
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[k] = x
            tail_idx[k] = i
        prev[i] = tail_idx[k - 1] if k else -1
    out: list[int] = []
    i = tail_idx[-1] if tail_idx else -1
    while i != -1:
        out.append(a[i])
        i = prev[i]
    return out[::-1]

Mini-project

pixi init lcsdiff && cd lcsdiff
pixi add python pytest
pixi run python lcsdiff.py old.txt new.txt
pixi run pytest -q

  def greet(name):
-     print("Hello " + name)
+     print(f"Hello, {name}!")
  greet("Ada")
+ greet("Grace")

Quiz

Recap

• DP = optimal substructure + overlapping subproblems. Cost = number of states × work per state.
• Top-down with functools.cache is quickest to write; bottom-up tabulation is faster, has no recursion limit, and enables rolling arrays.
• The five-step recipe: define the state in words, write the recurrence from the last decision, base cases, evaluation order, location of the answer (and plan reconstruction).
• Loop order and direction are part of the meaning: coins-outer counts combinations; downward capacity is 0/1 knapsack, upward is unbounded.
• Two-sequence problems (LCS, edit distance) index by prefix lengths; "ending at i" states (LIS) fix the last element.
• Reconstruct by re-deriving decisions from the full table or by storing choice pointers.

Going further

• functools.cache and lru_cache
• bisect: array bisection
• difflib: helpers for computing deltas
• Next: M33 Greedy Algorithms & Backtracking, and the Puzzle Solver Suite project, which uses knapsack and weighted interval scheduling.