Dynamic programming II

1 · Longest common subsequence — the model 2-D DP advanced

Every time you open a pull request, you're looking at LCS. That green-and-red diff view — "these lines are unchanged, these were added, these were removed" — is a tool answering one question: what's the longest run of lines these two files share, in order? Once it knows that shared backbone, everything not on it is an edit. The very same algorithm aligns two DNA strands to find their common ancestry, and it's what git merge leans on to reconcile two branches. If you've ever trusted a diff, you've trusted LCS.

Here's the intuition before any grid appears. Think of two shopping lists and you want the longest set of items that appear on both, keeping the order — but the items don't have to be next to each other. That "not necessarily contiguous" clause is the whole reason this isn't a trivial substring search: you're allowed to skip over items on either list to keep the match going. A subsequence deletes characters without reordering; a substring is a contiguous block. LCS wants the longest common subsequence, so it can jump gaps.

Why does this need a 2-D table when D10's problems got by with one dimension? Because the state now depends on two moving positions — how far you've read into string A and how far into string B. The honest way to see it: stand at the end of both prefixes and ask a single question. Do the last two characters match? If they match, you've found one more character of common sequence — claim it (+1) and step both prefixes back one. If they don't match, one of those two characters can't be in the LCS, so you try dropping each and keep whichever gives the longer answer. That single decision, memoized over every (i, j) pair, is the algorithm.

The mistake almost everyone makes first is confusing subsequence with substring — writing a solution that resets the count to zero on a mismatch (that's the longest common substring, a different problem). In LCS a mismatch never punishes you; it just means "skip a character and carry the best score you already have forward." Keep that distinction sharp, because the recurrence encodes it exactly: matches add, mismatches merely propagate the max. That is also the clean contrast with edit distance in §2 — LCS maximizes matches over two moves; edit distance minimizes cost over three.

Now the precise definition. Given two strings, the LCS is the longest sequence appearing in both, in order (not necessarily contiguous). State: dp[i][j] = LCS length of prefixes A[:i] and B[:j]. Transition: if the last characters match, dp[i][j]=dp[i-1][j-1]+1; else max(dp[i-1][j], dp[i][j-1]). Complexity: Θ(m·n) time and space. It underpins diff, git merges, and DNA alignment.

pythondef lcs(a, b):
    m, n = len(a), len(b)
    dp = [[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]:
                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])
    # reconstruct by walking back from dp[m][n]
    i, j, out = m, n, []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

length, seq = lcs("AGCAT", "GAC")
print("LCS length:", length, "one LCS:", seq)
print(lcs("ABCBDAB", "BDCAB"))

LCS length: 2 one LCS: AC
(4, 'BCAB')

2 · Edit distance (Levenshtein) advanced

You type "recieve" and your phone quietly fixes it to "receive." How did it know? It didn't read your mind — it measured distance. Against every word in its dictionary it asked, "how many single-character tweaks would turn what they typed into this real word?" and offered the closest one. That measure is edit distance, and it's the same machinery behind fuzzy search ("did you mean…?"), plagiarism checkers, and the fuzzy-match logic that reconciles a customer name spelled three different ways across three databases.

An analogy that makes the three moves click: imagine transforming one word into another using only a keyboard, and you're charged one keystroke per change. You can substitute a letter (overtype one), delete a letter (backspace), or insert a letter (type a new one). Edit distance is simply the cheapest total keystrokes to get from A to B. "kitten" → "sitting" costs three: substitute k→s, substitute e→i, insert a trailing g. There's no shorter route, and the DP proves it by trying all of them implicitly.

This is LCS's twin, and seeing the family resemblance is the real lesson. Both walk a 2-D grid over prefixes of two strings; both hinge on "do the last characters match?" The difference is direction and arity. LCS maximizes over two moves and a mismatch is free; edit distance minimizes over three moves and a mismatch costs 1. When characters match, edit distance pays nothing and carries the diagonal dp[i-1][j-1] straight through — you already agree here, no keystroke needed. When they differ, you take 1 + the cheapest of the three neighbours: the diagonal (substitute), the cell above (delete), the cell to the left (insert).

The classic trap is scrambling which neighbour means which edit — and it's worth pinning down, because reversing insert and delete silently gives wrong answers on asymmetric inputs. The reliable mnemonic: the diagonal handles both characters at once (match or substitute), so it always moves both indices; a move that changes only i (the cell above) consumes a character of A without one of B — that's a delete; a move that changes only j (the cell to the left) is an insert. Get the base cases right too: transforming an empty string into a length-k string costs exactly k inserts, which is why the first row and column count up 0,1,2,3,….

Now the precise version. The edit distance is the minimum number of single-character insertions, deletions, or substitutions to turn one string into another — the engine behind spell-check and fuzzy search. State: dp[i][j] = distance between A[:i] and B[:j]. Transition: if chars match, carry dp[i-1][j-1]; else 1 + min of the three edits.

pythondef edit_distance(a, b):
    m, n = len(a), len(b)
    prev = list(range(n + 1))               # dp for i-1 row; base: transform "" -> b[:j]
    for i in range(1, m + 1):
        cur = [i] + [0] * n                 # base: transform a[:i] -> ""
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],   # substitute
                                 prev[j],       # delete
                                 cur[j - 1])    # insert
        prev = cur
    return prev[n]

print(edit_distance("kitten", "sitting"))      # 3
print(edit_distance("sunday", "saturday"))     # 3
print(edit_distance("", "abc"), edit_distance("abc", "abc"))

3
3
3 0

3 · 0/1 knapsack — pack under a budget expert

You have a $10,000 marketing budget and fifteen campaigns, each with a cost and a projected return. You can't run them all. Which subset spends at or under the budget for the most total return? That is the knapsack problem in a suit, and it's everywhere the moment a resource is finite: choosing which features fit in a release, which files to cache under a size cap, which cargo to load on a truck by weight. The name comes from the folk version — a hiker with a fixed-size pack choosing which items to bring — but the shape is universal: maximize value subject to a budget, taking each thing whole or not at all.

The "whole or not at all" is what the 0/1 in the name means, and it's the crux. You cannot take half a campaign or 0.3 of a truck. Every item is a binary yes/no. That innocent constraint is exactly why greedy fails and why this is genuinely hard — famously, 0/1 knapsack is NP-hard. Your gut says "sort by value-per-weight and grab the best ratios first," and that greedy heuristic is often close but sometimes wrong: a single heavy-but-fantastic item can beat three efficient small ones, and greedy never reconsiders. DP wins because it doesn't commit early — it tracks the best achievable value at every budget level simultaneously.

Picture a table where rows are items and columns are every budget from 0 up to W. Filling cell dp[i][w] asks one clean question about item i: do I take it or skip it? Skip it and you inherit the best value the earlier items managed at this same budget, dp[i-1][w]. Take it (only if it fits) and you get its value plus the best the earlier items could do with the leftover budget, val[i] + dp[i-1][w-wt[i]]. The answer is the better of those two. Because each cell only reads the row above, you can famously collapse the whole table to a single rolling array — which is the trick in the lab below.

Here is the mistake that costs people the interview, and it hides in one line. When you compress to a 1-D array, the direction you sweep the weight loop secretly decides which problem you're solving. Sweep the budget downward (high to low) and each item is used at most once — true 0/1 — because dp[w-wt] still reflects the state before this item was considered. Sweep upward and you'd read an already-updated cell, letting the same item be taken again and again — that silently becomes the unbounded (coin-change) knapsack. One reversed loop, an entirely different answer. The warning box after the lab drills this, because it's the single most common knapsack bug. Now the precise setup:

Given items with weights and values and a capacity W, choose a subset of maximum value fitting the budget — each item taken or not (0/1). State: dp[i][w] = best value using items 0..i within weight w. Transition: skip item i (dp[i-1][w]) or take it if it fits (val[i]+dp[i-1][w-wt[i]]). Complexity: Θ(nW) — pseudo-polynomial (depends on the numeric value of W).

pythondef knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):      # iterate DOWN so each item used once
            dp[w] = max(dp[w], val + dp[w - wt])
    return dp[W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print("capacity 7 ->", knapsack(weights, values, 7))   # 9 (items 3+5? -> 4+5=9)
print("capacity 10 ->", knapsack(weights, values, 10)) # 13

capacity 7 -> 9
capacity 10 -> 13

4 · Matrix-chain multiplication — interval DP expert

Here's a result that surprises everyone the first time. You have three matrices to multiply, A·B·C. The math says the grouping doesn't matter — (A·B)·C equals A·(B·C), same final matrix. But the work to compute them can differ by a factor of ten or a hundred. On real shapes, one parenthesization might do 26,000 scalar multiplications and another 260,000 — identical output, an order of magnitude of wasted compute. Deep-learning frameworks and query planners obsess over exactly this, because chained tensor and join operations live or die on getting the multiply order right.

Why does grouping change the cost when the answer is the same? Multiplying a p×q matrix by a q×r matrix costs p·q·r scalar multiplications and produces a p×r result. So an intermediate product's shape — which depends on how you grouped — feeds into the cost of the next multiply. Group so that big shared dimensions get eliminated early and you keep the intermediates small; group badly and you carry a fat intermediate matrix through an expensive second multiply. The associativity guarantees the number is right; only the effort changes.

This is your first interval DP, and the mental shift it demands is the whole point of the section. Instead of thinking "left to right," you think about ranges: what's the cheapest way to fully multiply matrices i through j? The key move — and the one beginners resist — is to reason about the last multiplication, the single top-level split point k where the chain finally breaks into a left group i..k and a right group k+1..j. Whatever k is, both sides are smaller, already-solved subproblems, and the cost is their two costs plus the price of combining the two resulting matrices. You don't know the best k, so you try them all and keep the minimum.

The subtlety that trips people is fill order, and it follows directly from the "smaller ranges first" idea. A range of length 5 depends on ranges of length 4, 3, 2, 1 — so you must have those computed before you touch the length-5 cell. That means you cannot iterate the table row by row like LCS; you iterate by increasing interval length, gap size 2 first, then 3, and so on. Get that loop order wrong and you'll read empty cells and produce garbage. This length-first sweep is the signature of every interval DP in this lesson (matrix-chain here, palindromic subsequence and burst balloons in the ladder). Now the precise recurrence:

Multiplying a chain of matrices is associative, but the order of parenthesization hugely changes the scalar-multiplication count. State: dp[i][j] = min cost to multiply matrices i..j. Transition: try every split point k and take the cheapest: dp[i][k]+dp[k+1][j]+p[i-1]·p[k]·p[j]. This is the prototypical interval DP: solve short intervals first, so fill by increasing length. Θ(n³).

pythondef matrix_chain(dims):
    """dims = [p0, p1, ..., pn]; matrix i has shape p[i-1] x p[i]."""
    n = len(dims) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):          # interval length; short first
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):           # try every split
                cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                dp[i][j] = min(dp[i][j], cost)
    return dp[1][n]

# matrices: 40x20, 20x30, 30x10, 10x30
print(matrix_chain([40, 20, 30, 10, 30]))   # 26000
print(matrix_chain([10, 20, 30]))           # 6000 (single way)

26000
6000

5 · Grid DP — paths and minimum cost advanced

Think of a delivery robot in a warehouse laid out as a grid, starting top-left, needing to reach the bottom-right, and only ever driving right or down. Two questions come up constantly: how many distinct routes exist? (useful for reasoning about redundancy) and which route is cheapest? when each cell carries a toll — a slow aisle, a congested corridor, a fee. Both are grid DP, and it shows up far beyond robots: image seam-carving, dynamic-time-warping for audio, and the alignment grids you just met in LCS and edit distance are all the same shape wearing different clothes.

Grid DP is the friendliest 2-D DP to build intuition on because the dependencies are so physical. The rule "only right or down" means there is exactly one way to arrive at any cell: from the neighbour directly above it or the one directly to its left. Nothing else can reach it. So the value of a cell is built purely from those two neighbours — for counting paths you add them (every route into the top cell plus every route into the left cell all funnel here), and for minimum cost you take the cheaper of the two and add the current cell's toll. The grid fills like water flowing from the top-left corner down and to the right.

An everyday way to feel the counting version: to stand on any cell you must have taken your last step either from above or from the left, so the number of ways to be here is simply the sum of the ways to have been in each of those two places. That's Pascal's triangle hiding in a rectangle — which is why the unique-paths count is a binomial coefficient, though the DP finds it without you knowing the formula.

The classic mistakes here are the edges, literally. The top row and left column have only one neighbour, not two — a cell in the top row can only be reached from its left, a cell in the left column only from above. Forget to seed those base cases specially and your recurrence reaches off the grid or reads a zero that should be a one, quietly corrupting everything downstream. And a subtle one for the space-saving rolling-row version: when you overwrite dp[j], the old value still sitting there is the "from above" contribution and dp[j-1] (already updated this pass) is the "from the left" — get that read order backwards and you double-count. The precise framing:

A grid where you may move only right or down is the friendliest 2-D DP: each cell depends on its top and left neighbours. Two staples: count paths to the bottom-right, and minimum path sum. Both are Θ(mn) and reduce to one row of space.

pythondef unique_paths(m, n):
    row = [1] * n                           # first row: one way to each cell
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]            # from top (old row[j]) + from left
    return row[n - 1]

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
    return dp[n - 1]

print("unique paths 3x7:", unique_paths(3, 7))     # 28
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print("min path sum:", min_path_sum(grid))          # 7 (1->3->1->1->1)

unique paths 3x7: 28
min path sum: 7

6 · Bitmask DP — exact small TSP expert

A field technician has twelve service calls to make today and wants the shortest driving loop that hits all of them and returns to the depot. That's the Traveling Salesman Problem, and the brute-force answer — try every ordering — is n!, which at twelve cities is already ~479 million routes and at twenty is more orderings than there are grains of sand on Earth. You cannot enumerate your way out. Yet routing software, PCB drilling machines, and warehouse pick-path optimizers solve exactly these instances every day. The trick that rescues small-but-real cases is bitmask DP.

The idea starts from a question: what actually distinguishes one partial route from another? Not the exact order you visited cities in — only two things matter going forward: which set of cities you've already visited, and which city you're standing in now. Two different orderings that visited the same set and ended in the same place are interchangeable from here on. That collapse — from "all orderings" down to "(visited-set, current-city)" — is what turns n! into something tractable. It's the same memoization instinct as every DP: throw away the parts of history that can't change the future.

So how do you use a set as a dictionary key efficiently? You pack it into a single integer — a bitmask. Picture n light switches in a row; switch k is ON if city k has been visited. Read that row of ON/OFF switches as a binary number and you have one compact integer standing in for a whole subset. Now the operations are just bit-twiddling: mask | (1<<j) flips switch j on ("mark j visited"), and (mask >> j) & 1 peeks at whether switch j is on. This is why the universe must be small (≤ ~20): there are 2ⁿ possible switch-settings, and that 2ⁿ is your state space.

Two things routinely bite people here. First, the iteration order: sweeping mask from 0 upward isn't arbitrary — a subset's integer is always larger than any subset with fewer bits that it extends, so going upward guarantees every state you depend on was computed before you reach it (that's the DP dependency order, for free). Second, be honest about the complexity: Held–Karp is Θ(2ⁿ·n²) — still exponential, just a vastly smaller exponential than n!. It's exact and practical to about n≈18, and beyond that you switch to heuristics or approximation (a later lesson). Don't oversell it as "fast"; sell it as "exact where brute force is hopeless." The formal statement:

When a state is a subset of a small universe (≤ ~20 elements), encode it as an integer bitmask: bit k set means element k is in the set. The Held–Karp TSP DP uses dp[mask][i] = cheapest route visiting exactly the cities in mask, ending at city i. Complexity: Θ(2ⁿ·n²) — exponential, but far below the n! of brute force, and exact for n≲18.

pythonfrom itertools import permutations

def tsp_held_karp(dist):
    n = len(dist)
    FULL = (1 << n) - 1
    # dp[mask][i]: min cost path visiting `mask`, ending at i (start fixed at city 0)
    dp = [[float("inf")] * n for _ in range(1 << n)]
    dp[1][0] = 0                            # start: only city 0 visited, at city 0
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float("inf") or not (mask >> i) & 1:
                continue
            for j in range(n):
                if (mask >> j) & 1:
                    continue                # j already visited
                nmask = mask | (1 << j)
                cost = dp[mask][i] + dist[i][j]
                if cost < dp[nmask][j]:
                    dp[nmask][j] = cost
    return min(dp[FULL][i] + dist[i][0] for i in range(n))  # return to start

def brute_tsp(dist):
    n = len(dist)
    best = float("inf")
    for perm in permutations(range(1, n)):
        route = [0] + list(perm) + [0]
        cost = sum(dist[route[k]][route[k + 1]] for k in range(len(route) - 1))
        best = min(best, cost)
    return best

dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print("Held-Karp:", tsp_held_karp(dist), " brute:", brute_tsp(dist))

Held-Karp: 80  brute: 80

Checkpoint expert

pythondef unique_paths_obstacles(grid):
    n = len(grid[0])
    dp = [0] * n
    dp[0] = 1 if grid[0][0] == 0 else 0
    for i, row_cells in enumerate(grid):
        for j in range(n):
            if row_cells[j] == 1:
                dp[j] = 0                   # obstacle: no paths through here
            elif j > 0:
                dp[j] += dp[j - 1]
    return dp[n - 1]

print(unique_paths_obstacles([[0,0,0],[0,1,0],[0,0,0]]))   # 2
print(unique_paths_obstacles([[0,1],[0,0]]))               # 1
print(unique_paths_obstacles([[1,0]]))                     # 0 (start blocked)

2
1
0

pythondef longest_pal_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1                        # single char is a palindrome of length 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (dp[i + 1][j - 1] if length > 2 else 0) + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

print(longest_pal_subseq("bbbab"))     # 4  -> "bbbb"
print(longest_pal_subseq("cbbd"))      # 2  -> "bb"
print(longest_pal_subseq("agbdba"))    # 5  -> "abdba"

4
2
5

pythondef knapsack_items(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt <= w:
                dp[i][w] = max(dp[i][w], val + dp[i - 1][w - wt])
    # reconstruct
    chosen, w = [], W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    chosen.reverse()
    return dp[n][W], chosen

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
best, items = knapsack_items(weights, values, 7)
print("value:", best, "items:", items,
      "weight:", sum(weights[i] for i in items))

value: 9 items: [1, 2] weight: 7

pythondef is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):               # patterns like a* matching empty string
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]
                one = dp[i - 1][j] and p[j - 2] in (s[i - 1], ".")
                dp[i][j] = zero or one
            elif p[j - 1] in (s[i - 1], "."):
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

for s, p in [("aa","a"), ("aa","a*"), ("ab",".*"), ("mississippi","mis*is*p*.")]:
    print(f"{s!r} ~ {p!r}: {is_match(s, p)}")

'aa' ~ 'a': False
'aa' ~ 'a*': True
'ab' ~ '.*': True
'mississippi' ~ 'mis*is*p*.': False

pythondef max_coins(nums):
    balloons = [1] + nums + [1]
    n = len(balloons)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):              # gap between i and j
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):       # k = LAST balloon burst in (i, j)
                coins = balloons[i] * balloons[k] * balloons[j]
                dp[i][j] = max(dp[i][j], coins + dp[i][k] + dp[k][j])
    return dp[0][n - 1]

print(max_coins([3, 1, 5, 8]))     # 167
print(max_coins([1, 5]))           # 10

167
10

pythonfrom itertools import permutations

def max_assignment(profit):
    J = len(profit)
    M = len(profit[0])
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def best(j, used_mask):
        if j == J:
            return 0
        result = best(j + 1, used_mask)          # skip job j
        for m in range(M):
            if not (used_mask >> m) & 1 and profit[j][m] >= 0:
                result = max(result,
                             profit[j][m] + best(j + 1, used_mask | (1 << m)))
        return result

    return best(0, 0)

def brute(profit):
    J, M = len(profit), len(profit[0])
    best = 0
    # try assigning each subset of jobs to distinct machines
    for r in range(min(J, M) + 1):
        for jobs in permutations(range(J), r):
            for machines in permutations(range(M), r):
                if all(profit[j][m] >= 0 for j, m in zip(jobs, machines)):
                    best = max(best, sum(profit[j][m] for j, m in zip(jobs, machines)))
    return best

profit = [[5, 1, -1],
          [-1, 8, 3],
          [4, 2, 6]]
print("bitmask DP:", max_assignment(profit), " brute:", brute(profit))

bitmask DP: 19  brute: 19