06 · Dynamic programming: choose a sufficient state

Dynamic programming does not mean “make a table and guess a recurrence.” It means identify subproblems whose answers can be reused, then evaluate their dependency graph without recomputing the same state. The number of states can still be exponential; a DP is not automatically polynomial in the input's encoded size.

MIT's first DP notes organize the method around subproblems, relationships, topological order, base cases, the original problem and time analysis. Use that checklist before choosing memoization or a table.

One decision reveals the state

Choose optional jobs with positive integer costs and nonnegative integer values under an integer budget. Each listed job may be selected at most once. For this exercise, there are no prerequisite constraints; this is a different optimization question from the previous lesson. Adding dependencies changes which state is sufficient.

Define best(i, c) as the maximum value using only the first i jobs with total cost at most c. The next decision is exhaustive: omit job i, or include it once if it fits. The include branch adds its value and uses only the previous jobs with reduced capacity. The base with zero jobs has value zero for every capacity because the empty selection is allowed.

A two-dimensional table follows directly. We can compress it to one row because each row depends only on the previous one, but the direction of overwriting now matters. For each job, scan capacities downward. Then dp[c - cost] still refers to the previous row. Scan upward instead and it may already include the current job, silently allowing reuse.

from itertools import product
 
 
def knapsack01(items, capacity):
    if type(capacity) is not int or capacity < 0:
        raise ValueError("capacity must be a nonnegative integer")
    if any(type(w) is not int or w <= 0 or type(v) is not int or v < 0
           for w, v in items):
        raise ValueError("positive integer costs and nonnegative integer values required")
    dp = [0] * (capacity + 1)
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]
 
 
def brute01(items, capacity):
    best = 0
    for mask in range(1 << len(items)):
        selected = [items[i] for i in range(len(items)) if mask & (1 << i)]
        if sum(w for w, _ in selected) <= capacity:
            best = max(best, sum(v for _, v in selected))
    return best
 
assert knapsack01([(2, 3)], 4) == 3  # upward iteration would wrongly give 6
assert knapsack01([(2, 3), (3, 5), (4, 6)], 5) == 8
for n in range(5):
    for items in product(((1, 0), (1, 2), (2, 3)), repeat=n):
        for capacity in range(7):
            assert knapsack01(items, capacity) == brute01(items, capacity)

For items (2, 3), (3, 5) and capacity five, after the first item the row is [0, 0, 3, 3, 3, 3]. The second item first updates capacity five from three to dp[2] + 5 = 8. When it later updates capacity three, that cannot affect the already-processed capacity five. The order implements “each listed item at most once.” Equal item descriptions at different list positions still represent separate available items.

There are O(nW) transitions and O(W) storage for n items and capacity W, counting integer operations at unit cost. This is pseudopolynomial: writing W in binary takes only about log₂ W bits. A capacity of a billion creates a billion-sized table even when the input file is tiny. MIT's pseudopolynomial DP notes explicitly distinguish numeric magnitude from encoded input size.

Exact amount is not capacity at most

For the fewest coins forming an exact amount, an unreachable positive amount must not begin at zero. Otherwise the recurrence treats an impossible remainder as free. Use a sentinel larger than any possible valid coin count, with only amount zero initialized to zero.

from collections import deque
from itertools import combinations
 
 
def min_coins(coins, amount):
    if type(amount) is not int or amount < 0:
        raise ValueError("amount must be a nonnegative integer")
    if any(type(c) is not int or c <= 0 for c in coins):
        raise ValueError("coins must be positive integers")
    coins = sorted(set(coins))
    unreachable = amount + 1
    dp = [0] + [unreachable] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                dp[total] = min(dp[total], dp[total - coin] + 1)
    return -1 if dp[amount] == unreachable else dp[amount]
 
 
def coins_bfs(coins, amount):
    queue = deque([(0, 0)])
    seen = {0}
    while queue:
        total, count = queue.popleft()
        if total == amount:
            return count
        for coin in coins:
            nxt = total + coin
            if nxt <= amount and nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, count + 1))
    return -1
 
assert min_coins([1, 3, 4], 6) == 2  # 3+3; largest-first gives 4+1+1
assert min_coins([2], 3) == -1
assert min_coins([], 0) == 0
for size in range(5):
    for coins in combinations(range(1, 5), size):
        for amount in range(16):
            assert min_coins(coins, amount) == coins_bfs(coins, amount)

Positive coins make every dependency a smaller amount, so ascending totals are a topological order. They also justify the sentinel: any attainable amount can be formed with at most amount coins, since each coin contributes at least one. Zero coins would create self-dependencies; negative coins would destroy this bounded acyclic model. Reusing a coin is permitted because a smaller solved total may already use it.

The BFS oracle treats each amount as a vertex and each added coin as one unit-cost edge. It reaches the same answer by a different evaluation strategy. This is stronger evidence than copying the table recurrence into a second function, but it still verifies only the enumerated finite cases. With m distinct coins the table uses O(mA) transitions and O(A) storage, plus coin deduplication/sorting, for amount A.

Counting changes the question again

For denominations one and two and amount three, the unordered multisets are 1+1+1 and 1+2: two combinations. Ordered sequences are 1+1+1, 1+2, and 2+1: three sequences. “Ways” is too vague a contract.

def combinations_count(coins, amount):
    ways = [1] + [0] * amount
    for coin in sorted(set(coins)):
        for total in range(coin, amount + 1):
            ways[total] += ways[total - coin]
    return ways[amount]
 
 
def sequences_count(coins, amount):
    ways = [1] + [0] * amount
    for total in range(1, amount + 1):
        for coin in sorted(set(coins)):
            if coin <= total:
                ways[total] += ways[total - coin]
    return ways[amount]
 
# Internal helpers: positive integer denominations, nonnegative integer amount.
assert combinations_count([1, 2], 3) == 2
assert sequences_count([1, 2], 3) == 3
assert combinations_count([1, 1, 2], 3) == 2

Coin-outer order restricts each construction to the current and earlier denomination types; each multiset gets one construction order. Total-outer order partitions sequences by their last coin, distinguishing 1+2 from 2+1. These helpers state preconditions instead of repeating the input boundary. They are not valid for zero or negative denominations.

A prior curriculum example claimed a best unbounded value of 130 for weights [1, 3, 4], values [15, 50, 60], capacity eight, but annotated it as 4+4 -> 60+60. The arithmetic was inconsistent: two fours give 120; 3+3+1+1 gives 130. That original is archived, not certified by this replacement. Also, zero-initialized maximum-value tables mean “at most capacity,” not “exactly fill capacity.”

Exercises

1. Change knapsack to require exact fill. What base values change?
2. Why can selecting the largest coin first fail? Use the executed example rather than an appeal to a pattern name.
3. If jobs have prerequisites, can (i, capacity) alone still summarize everything needed?

Exit artifact: write state meaning, base, recurrence, order, answer location and complexity before code. The notebook capstone can use dependency ordering without solving this harder constrained optimization variant.

Next: Relational data and transactions.