Dynamic Programming II: The Classic Patterns

1Six shapes

Almost every DP problem you meet is a variation of one of six templates. Recognising which is most of the work.

Chapter 25 gave the grammar: state, transition, base case, order. This chapter is the vocabulary — the handful of state shapes that recur so often that recognising one saves you the entire derivation.

2Knapsack

A budget that choices consume. The single most common shape, and the one with the most variants.

0/1 knapsack. Items each have a weight and a value; the bag holds W; each item is taken whole or not at all. Chapter 24 showed greedy fails here. The DP does not.

def knapsack(items, W):
    """items: list of (value, weight). Returns the best value that fits in W."""
    dp = [[0] * (W + 1) for _ in range(len(items) + 1)]

    for i, (v, w) in enumerate(items, start=1):
        for cap in range(W + 1):
            dp[i][cap] = dp[i - 1][cap]                  # skip item i
            if w <= cap:                                  # or take it, if it fits
                dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - w] + v)

    return dp[len(items)][W]

Read the state out loud, as Chapter 25 insisted: “dp[i][cap] is the best value obtainable using only the first i items, with a bag of capacity cap.” Both indices are needed, so the table is 2-D, and that follows from the sentence rather than from guesswork.

for v, w in items:
    for cap in range(W, w - 1, -1):        # BACKWARDS
        dp[cap] = max(dp[cap], dp[cap - w] + v)

3Two sequences

One string down the side, the other along the top, and a rule for each cell. The second most common shape.

Whenever a problem compares two sequences — align them, transform one into the other, find what they share — the state is almost always “the answer for the first i of one and the first j of the other”.

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i            # delete every character of a
    for j in range(m + 1):
        dp[0][j] = j            # insert every character of b

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]           # free: characters agree
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete from a
                                   dp[i][j - 1],      # insert into a
                                   dp[i - 1][j - 1])  # substitute

    return dp[n][m]

Longest common subsequence is the same table with a different rule, and is worth putting side by side because the resemblance is the point:

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1       # extend the match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one character

    return dp[n][m]

Relatives of the same shape, all with dp[i][j] over two sequences: longest common substring (contiguous — reset to 0 on a mismatch instead of taking a max), sequence alignment with custom gap penalties (the Needleman–Wunsch algorithm in bioinformatics), regular-expression and wildcard matching, and “is s an interleaving of a and b”.

4Subsequences, partitions and grids

One array with a 1-D state; a boolean reachability table; and a board you walk across.

Subsequence in one array. The state is “the best answer ending at index i”. Chapter 25 used it for longest increasing subsequence, and the “ending at” clause is what makes the transition possible — you cannot ask whether nums[i] extends something unless you know what it would extend.

# The O(n log n) LIS: keep the smallest possible tail for each length.
import bisect

def lis_fast(nums):
    tails = []                       # tails[k] = smallest tail of an increasing run of length k+1
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)          # x extends the longest run so far
        else:
            tails[i] = x             # x gives a better (smaller) tail for that length
    return len(tails)

Partition and subset-sum. “Can any subset reach exactly this total?” is knapsack with a boolean instead of a value:

def can_partition(nums):
    """Can nums be split into two halves of equal sum?"""
    total = sum(nums)
    if total % 2:
        return False                     # odd total: impossible, no work needed
    target = total // 2

    reachable = [False] * (target + 1)
    reachable[0] = True                  # the empty subset reaches 0
    for x in nums:
        for s in range(target, x - 1, -1):    # backwards: each item used once
            if reachable[s - x]:
                reachable[s] = True

    return reachable[target]

Notice the backwards loop again, and for the same reason. Recognising “split into two equal halves” as “reach exactly total/2” as “0/1 knapsack with boolean values” is the entire solution; the code afterwards is six lines.

bits = 1
for x in nums:
    bits |= bits << x
return (bits >> target) & 1

Grids. dp[r][c] built from the cells you could have come from. You did unique-paths-with-obstacles in Chapter 25; the variants are minimum path sum, maximum gold collected, and “largest square of 1s”:

def largest_square(grid):
    """Side length of the largest all-ones square."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    best = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                if r == 0 or c == 0:
                    dp[r][c] = 1
                else:
                    # a square ending here is limited by all THREE neighbours
                    dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])
                best = max(best, dp[r][c])

    return best

5Interval DP

The sixth shape, and the one people miss. When the answer depends on what you do LAST, loop over lengths.

So the state is a range: “dp[i][j] is the best answer for the elements strictly between i and j”, and the transition tries every choice of the last element in that range.

def matrix_chain(dims):
    """dims[i] x dims[i+1] is matrix i. Fewest scalar multiplications to multiply them all."""
    n = len(dims) - 1                       # number of matrices
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):          # <-- loop over LENGTH, not over i and j
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):           # the LAST multiplication splits at k
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                if cost < dp[i][j]:
                    dp[i][j] = cost

    return dp[0][n - 1]

The family is small but distinctive: matrix chain multiplication, burst balloons, optimal binary search trees, palindrome partitioning, and “merge stones”. All share the “what happens last” inversion and the length-first loop.

6From wording to recurrence

A checklist for turning an unfamiliar problem into one of the six.

Work through these in order. The first one that fits is usually right.

1. Is there a budget, capacity or count that choices consume? → knapsack. The budget is a dimension of the state. Ask immediately whether items repeat: that decides the loop direction.
2. Are there two sequences? → dp[i][j] over prefixes of each.
3. One sequence, and the answer is a subsequence or a run? → dp[i] = best ending at i.
4. “Can we reach exactly…” or “split into equal…”? → boolean subset-sum.
5. A 2-D board with restricted moves? → grid DP.
6. Does the cost of a choice depend on its neighbours at the time? → interval DP. Ask what happens last.

>_Playground

0/1 versus unbounded knapsack from the same code, edit distance with the actual edit script, and the bitset partition trick.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.