13.2 Classic Dynamic Programming Problems

Prerequisites: Dynamic Programming Basics. This lesson uses the 0-1 Knapsack problem to practice capacity dimensioning and the Longest Common Subsequence (LCS) and edit distance problems to explore two-sequence prefix dynamics. Code explicitly defines input contracts and demonstrates the meaning of traversal direction through one-dimensional optimization.

Work Backward from the Last Choice

The first asks how to select supplies within a limited capacity. The second compares two logs to determine the length of their shared subsequence. The third calculates the minimum number of operations needed to transform one record into another. Though they appear distinct, their modeling steps are identical: first, write a complete definition for the index of dp, then work backward from the final choice to establish dependencies.

A Working Reference Implementation

Knapsack weights and values must be equal-length sequences: weights are positive integers and values are integers. Selecting nothing is allowed, so negative values cannot force a negative answer. Capacity and amount are non-negative integers. Coins may be any iterable of positive integers; duplicates preserve the answer but repeat work. LCS and edit distance accept strings only. No function modifies its input. Numeric contract violations raise ValueError; invalid string types raise TypeError.

def knapsack_01(weights, values, capacity):
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal length")
    if not isinstance(capacity, int) or capacity < 0:
        raise ValueError("capacity must be a non-negative integer")
    if any(not isinstance(weight, int) or weight <= 0 for weight in weights):
        raise ValueError("weights must be positive integers")
    if any(not isinstance(value, int) for value in values):
        raise ValueError("values must be integers")

    best = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for remaining in range(capacity, weight - 1, -1):
            best[remaining] = max(
                best[remaining],
                best[remaining - weight] + value,
            )
    return best[capacity]

def lcs_length(first, second):
    if not isinstance(first, str) or not isinstance(second, str):
        raise TypeError("first and second must be strings")
    previous = [0] * (len(second) + 1)
    for first_char in first:
        current = [0]
        for column, second_char in enumerate(second, start=1):
            if first_char == second_char:
                current.append(previous[column - 1] + 1)
            else:
                current.append(max(previous[column], current[column - 1]))
        previous = current
    return previous[-1]

def edit_distance(source, target):
    if not isinstance(source, str) or not isinstance(target, str):
        raise TypeError("source and target must be strings")
    previous = list(range(len(target) + 1))
    for row, source_char in enumerate(source, start=1):
        current = [row]
        for column, target_char in enumerate(target, start=1):
            if source_char == target_char:
                current.append(previous[column - 1])
            else:
                current.append(1 + min(
                    previous[column],      # Delete source_char
                    current[column - 1],   # Insert target_char
                    previous[column - 1],  # Replace
                ))
        previous = current
    return previous[-1]

def min_coin_count(coins, amount):
    if not isinstance(amount, int) or amount < 0:
        raise ValueError("amount must be a non-negative integer")
    coins = list(coins)
    if any(not isinstance(coin, int) or coin <= 0 for coin in coins):
        raise ValueError("coins must be positive integers")

    unreachable = amount + 1
    best = [unreachable] * (amount + 1)
    best[0] = 0
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                best[current] = min(best[current], best[current - coin] + 1)
    return -1 if best[amount] == unreachable else best[amount]

if __name__ == "__main__":
    assert knapsack_01([2, 3, 4, 5], [3, 4, 5, 6], 8) == 10
    assert knapsack_01([], [], 8) == 0
    assert lcs_length("abcde", "ace") == 3
    assert lcs_length("", "ace") == 0
    assert edit_distance("horse", "ros") == 3
    assert edit_distance("", "abc") == 3
    assert min_coin_count([1, 2, 5], 11) == 3
    assert min_coin_count([2], 3) == -1
    print("Classic DP Check passed")

0-1 Knapsack: Backward Traversal to Preserve Previous State

The two-dimensional definition is:

dp[i][c] = maximum value achievable when considering only the first i items and capacity not exceeding c

For the i-th item, there are only two possible choices: not selecting it or selecting it exactly once. When compressed into one dimension, best[c] simultaneously holds the state from the previous iteration and the current one. The capacity must be traversed in descending order so that when reading best[c-weight], it still represents the state from before processing the current item.

If traversal were done in ascending order, the result for smaller capacities written during the current iteration would be read again in the same pass, effectively allowing the same item to be reused multiple times. This would transform the problem into the unbounded knapsack. The phrase "0-1 backward, unbounded forward" is not a mnemonic in itself, but rather a precise statement of whether the current item can be reused during the same iteration.

The optimal value of 10 in the example comes from selecting items with weights 3 and 5 and values 4 and 6, respectively. Returning only the value to the caller does not convey which items were chosen; to reconstruct the actual selection, preserve the two-dimensional table or historical choices that later updates cannot overwrite. Attaching a mutable predecessor-capacity pointer to each one-dimensional cell can make reconstruction read a later state.

For n items and positive capacity W, the usual bounds are O(nW) time and O(W) space. Including n=0 or W=0, initialization and input checks give O(nW+n+W+1) time and O(W+1) space. This counts integer operations as constant time; W is the numeric capacity, not its bit length. Thus, this is a pseudo-polynomial algorithm: if the capacity is represented in binary and its value is very large, O(W) cannot simply be described as a polynomial in input size.

LCS: Subsequence Does Not Require Continuity

dp[i][j] represents the length of the longest common subsequence between the first i and j characters of two sequences. If the last characters match, we can append that character to the common subsequence derived from the shorter prefixes; if they don't match, then each optimal alignment omits at least one of the two trailing characters, so we take the maximum of either removing the last character from the first sequence or from the second sequence.

This page only returns the length of the subsequence, reducing space complexity from O(mn) to O(n) using just two rows. To reconstruct the actual subsequence, additional information about choices must be preserved, or a path-recomputable algorithm must be used. For nonempty strings, time is Θ(mn), where m and n are the lengths of the first and second strings. Including empty inputs, the bounds are Θ((m+1)(n+1)) time and Θ(n+1) space. Putting the shorter string second reduces the row width to the shorter length.

LCS differs from the longest common substring: a substring must appear consecutively, and when characters mismatch, the state typically resets to zero; in contrast, a subsequence only requires that the relative order of characters be preserved.

Edit Distance: Three Operations Correspond to Three Neighboring States

dp[i][j] represents the minimum number of operations required to transform the first i characters of the source string into the first j characters of the target string. When characters do not match:

• Delete the last character from the source: dp[i-1][j];
• Insert the last character from the target into the source: dp[i][j-1];
• Replace the last character of the source with the last character of the target: dp[i-1][j-1].

Each operation adds 1. Converting an empty prefix to length j requires j insertions, which initializes the first row. Converting a prefix of length i to an empty string requires i deletions, which initializes the first column. For nonempty strings, time is Θ(mn) and two-row space is Θ(n); including empty inputs, these become Θ((m+1)(n+1)) and Θ(n+1). Here m and n are the source and target lengths.

This page uses Unicode code point sequences for Python strings, comparing character by character without normalization. For example, edit_distance("é", "e\u0301") is 2; normalizing both strings to NFC first makes it 0. Python’s Unicode normalization API can unify canonically equivalent forms. It does not equate all visually similar characters or segment text into user-perceived characters (grapheme clusters). Swapping adjacent characters is also not a separate operation here.

Coin Change: Some States Are Unreachable

best[a] represents the minimum number of coins needed to make amount a. Each coin denomination can be reused, and transitions proceed by reducing the target amount. We use amount+1 as an unreachable sentinel because each coin has integer value at least 1, so any solution for amount uses at most amount coins. A denomination of 1 need not actually exist.

If any denomination is zero or negative, the dependency no longer strictly points to smaller amounts, and the approach is immediately rejected. Amount 0 returns 0. With no coins, a positive amount returns -1. For k denominations and amount A, including the coin copy and initialization, time is O(k+A(k+1)+1) and space is O(k+A+1). This table indexed by amount is also pseudo-polynomial.

Check the Meaning of States

1. Rewrite the knapsack capacity loop to be forward-directed, and use a single item to demonstrate that it will be reused.
2. Preserve the selection path in the knapsack solution, and define a tie-breaking rule when multiple optimal solutions exist.
3. Manually compute the table for LCS("abc", "bac"), and observe that the optimal sequence may not be unique.
4. Assign different costs to insertions, deletions, and substitutions in edit distance, what boundaries must be adjusted accordingly?
5. Use BFS to model coin change for small denominations as a shortest path problem, and compare the results randomly against the DP solution.

Check the Dependencies Before Compressing

The loop direction in capacity DP determines whether the current item can be reused; in two-sequence DP, the three neighboring states correspond to deletion, insertion, substitution, or skipping the end. The state definition must be precise enough to provide a verifiable source for boundaries and traversal order.

The next chapter turns to Greedy Algorithms: some problems do not require retaining all candidates, only making a locally optimal and provably safe choice.