Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 13

Dynamic programming: state, order, and reconstruction

Define reusable subproblems and a valid dependency order before compressing storage or reconstructing a solution.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A table entry needs a sentence of meaning
Minimize over every valid last choice
Compressed storage still represents conceptual layers

A table entry needs a sentence of meaning

Dynamic programming reuses solutions to overlapping subproblems. Start by defining exactly what each state means, its accepted parameters, and which smaller states it depends on. Then define base cases and an evaluation order that respects those dependencies. A table full of numbers is not a model by itself. For minimum coin count, state[a] can mean the minimum number of permitted positive coins whose values sum exactly to amount a, with unlimited reuse. This differs from counting combinations, choosing each coin once, or accepting a sum no greater than a. Each variation changes the recurrence.

Minimize over every valid last choice

The first program considers the final coin of an exact amount. Removing a positive coin leaves a strictly smaller amount, so increasing amount order is valid. Unreachable states remain infinity, while amount zero needs zero coins. A predecessor coin records a choice only when it improves the count. Following these choices reconstructs one optimum, and positivity guarantees the remaining amount decreases to zero. The code rejects zero or negative denominations because they would invalidate this dependency argument. It returns None for an unreachable target instead of confusing absence with an accepted zero-coin solution.

python Self-contained Python3 algorithm example using synthetic local data.

from math import inf

def minimum_coins(coins, amount):
    if type(amount) is not int or amount < 0:
        raise ValueError("Amount must be a nonnegative integer")
    if any(type(coin) is not int or coin <= 0 for coin in coins):
        raise ValueError("Coins must be positive integers")
    best = [inf] * (amount + 1)
    parent = [None] * (amount + 1)
    best[0] = 0
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current and best[current - coin] + 1 < best[current]:
                best[current] = best[current - coin] + 1
                parent[current] = coin
    if best[amount] == inf:
        return None
    chosen, remaining = [], amount
    while remaining:
        coin = parent[remaining]
        chosen.append(coin)
        remaining -= coin
    return best[amount], chosen

print(minimum_coins([1, 3, 4], 6))
print(minimum_coins([4, 6], 5))
print(minimum_coins([1, 3], 0))

Expected output

(2, [3, 3])
None
(0, [])

Exact6 uses two3 coins. Amount5 cannot be formed from4 and6, while zero has the empty solution.

Compressed storage still represents conceptual layers

In zero-one knapsack, each item can be used at most once. A conceptual state includes both the processed-item prefix and capacity. The second program stores only one capacity row, updating capacities downward so a transition reads the previous item layer. Upward iteration would read a value already improved with the same item and accidentally permit reuse. The state here means best value with weight at most capacity, so zero initialization permits the empty selection. An exact-weight formulation needs a different unreachable-state initialization. Compression changes storage, not the underlying dependency contract.

python Self-contained Python3 algorithm example using synthetic local data.

def zero_one_knapsack(items, capacity):
    if type(capacity) is not int or capacity < 0:
        raise ValueError("Capacity must be a nonnegative integer")
    best = [0] * (capacity + 1)
    for weight, value in items:
        if type(weight) is not int or weight <= 0:
            raise ValueError("Weights must be positive integers")
        for current in range(capacity, weight - 1, -1):
            best[current] = max(best[current], best[current - weight] + value)
    return best[capacity]

print(zero_one_knapsack([(2, 3), (3, 4)], 4))
print(zero_one_knapsack([(2, 3)], 0))

Expected output

4
0

The weight2 item cannot be used twice. Descending iteration preserves the previous-item meaning of the source cell.

Numeric bounds can make complexity pseudopolynomial

For c denominations and target A, the coin table uses O(cA) transitions and O(A) storage, excluding reconstruction output. Knapsack uses O(nC) transitions for n items and capacity C. These bounds depend on numeric magnitude, while writing A or C in binary takes only logarithmically many bits. Therefore the algorithms are pseudopolynomial in general input encoding, not polynomial merely because they use nested loops over integers. Large values can make a table impractical despite a small number of items. State arithmetic assumptions and accepted resource limits without prescribing a universal maximum.

Reconstruction needs consistency with the optimum

A correct objective value does not guarantee a correct reconstructed choice list. Every stored predecessor must correspond to the transition that established that state, and its chain must terminate under the dependency measure. Memory compression can overwrite information needed for reconstruction, especially in item-based problems. Preserve separate predecessor layers, recompute decisions deliberately, or use another proven recovery strategy. Also define tie behavior: several optima may exist, and returning one valid optimum is different from counting all or selecting a lexicographically preferred optimum. Do not infer a unique solution from a unique numeric minimum.

Compare tiny states with an independent enumeration

For small coin targets, a BFS over reachable amounts provides an independent minimum-edge reference. Verify the reconstructed coins belong to the accepted set, sum to the target, and have the reported count. For tiny knapsack fixtures, enumerate subsets and compare the best feasible value. Include unreachable exact amounts, zero target, duplicate denominations, an item heavier than capacity, and the reuse counterexample. These tests are deliberately bounded local computations. They complement the recurrence and layer invariant, and do not claim that finite enumeration proves every input or that large tables were benchmarked.

Common errors and fixes

A zero-one item is reused within one update

Why it happens: Compressed capacities were traversed upward.
How to fix it: Traverse downward to read the previous item layer.
Prevent it next time: Test one weight2,value3 item at capacity4.

An unreachable amount looks like an empty solution

Why it happens: All states were initialized as accepted zero cost.
How to fix it: Keep unreachable distinct and initialize only valid base states.
Prevent it next time: Test zero separately from a positive unreachable amount.

Reconstruction loops or returns inconsistent choices

Why it happens: Predecessors do not follow a decreasing valid transition.
How to fix it: Store choices alongside proven improvements and validate the chain.
Prevent it next time: Check membership, sum, count, and termination.

Check your understanding

1. Why does largest-first fail for coins1,3,4 and amount6?

Show worked solution

It chooses4 then1 then1, using three coins, while3+3 uses two. A local large denomination does not guarantee a globally minimal count. The dynamic program considers every permitted final coin and compares complete smaller solutions.

2. Why does the knapsack result4 differ from an unbounded result6?