Dynamic Programming: Advanced Patterns

0/1 Knapsack

Lesson 17's fractional knapsack could split any item to use capacity perfectly. 0/1 knapsack removes that freedom, each item is either taken whole or left behind entirely, and that single constraint is exactly what broke the greedy ratio strategy. DP handles it by building a table where table[i][c] holds the best value achievable using only the first i items with capacity c. Each cell has just two options to consider: skip item i, or take it (if it fits) and add its value to the best solution for the remaining capacity.

def knapsack_01(items: list[tuple[int, int]], capacity: int) -> int:
    # items: list of (value, weight) pairs
    n = len(items)
    table = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        value, weight = items[i - 1]
        for c in range(capacity + 1):
            table[i][c] = table[i - 1][c]              # option 1: skip this item
            if weight <= c:
                table[i][c] = max(
                    table[i][c],
                    table[i - 1][c - weight] + value,   # option 2: take it
                )
    return table[n][capacity]

# same (value, weight) pairs and capacity as Lesson 17's fractional knapsack
items = [(60, 10), (100, 20), (120, 30)]
print(knapsack_01(items, 50))

220

The table makes the decision visible. Each row adds one more item to the set under consideration, each column is an amount of available capacity, and every cell holds the best value reachable with those items and that capacity. The bottom-right cell is the answer, 220. Tracing the highlighted backtrace up from it shows exactly which items that 220 is made of:

Longest Common Subsequence

Given two sequences, find the longest sequence of characters that appears in both, in order, but not necessarily contiguously. This is the algorithm behind diff-style tools and DNA sequence alignment. The table this time is indexed by a position in each string: table[i][j] holds the LCS length of the first i characters of a and the first j characters of b. When the current characters match, extend the diagonal neighbor's subsequence by one, otherwise take the best of skipping a character from either side.

def lcs_length(a: str, b: str) -> int:
    n, m = len(a), len(b)
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1        # characters match, extend the subsequence
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])  # skip a char from one side
    return table[n][m]

print(lcs_length("ABCBDAB", "BDCAB"))

4

The table only stores lengths, but walking back through it from table[n][m] toward table[0][0], following whichever choice produced each cell's value, recovers the actual matching characters:

def lcs_string(a: str, b: str) -> str:
    n, m = len(a), len(b)
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])

    # walk back through the table to recover the actual characters
    i, j = n, m
    result = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])
            i -= 1
            j -= 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))

print(lcs_string("ABCBDAB", "BDCAB"))

BCAB

The code is hard to follow in the abstract, so here is the actual filled table for "ABCBDAB" against "BDCAB". Each cell is the LCS length of the prefixes that lead to it, and the bottom-right corner holds the final answer, 4. The highlighted trail is the backtrace: starting from that corner and walking toward table[0][0], a diagonal step on a character match picks up one letter of the result, while an up or left step skips a character from one string:

The General Pattern

Both problems above follow the same recipe once the table's meaning is pinned down: one dimension per independent piece of state needed to describe a subproblem (item index and remaining capacity for knapsack, a position in each string for LCS), and a transition rule that builds each cell from cells that were already computed. Extending this further is exactly how DP problems get harder in practice: three interacting constraints (three items being tracked, or a string plus a budget plus a count) mean a 3D table, following the identical logic, just with one more index to loop over.

Both tables above only ever read from the previous row (table[i-1] or table[i-1][...]), never anything further back. That means the full 2D table isn't strictly required, keeping just the current row and the previous row (or even a single row, updated carefully in the right direction for knapsack) is enough, cutting the space from O(n × capacity) down to O(capacity). This is the same space-optimization idea Lesson 18 applied to Fibonacci, just one dimension larger.

Complexity at a Glance

Both problems still run in polynomial time, a direct result of only ever solving each distinct (item, capacity) or (position, position) pair once, exactly Lesson 18's overlapping-subproblems principle, just applied across two dimensions instead of one.