Designing a Dynamic Program: State, Transition, Order

Every dynamic program is the same three decisions:

1. The state. What arguments identify a subproblem?
2. The transition. How is a state's value built from other states?
3. The order. In what sequence can they be evaluated so dependencies are ready?

Everything else, the arrays, the loop bounds, the base cases, is bookkeeping that follows from those three.

Most people learn dynamic programming as a catalogue of recurrences: the knapsack one, the edit distance one, the coin change one. That does not transfer, because the next problem is not in the catalogue. Choosing a state does transfer. Once the state is right, the transition is usually forced, the order is read off the transition, and the running time falls out of both without any further analysis.

The state must capture everything about the past that affects the future, and nothing else. That is the whole specification, and both halves bite.

Too little and the program is wrong, silently. The recurrence still runs and still returns a number; the number is just not the answer.

Too much and the program is slow. Every redundant field multiplies the state space, and the running time with it.

The practical test is a question you can ask out loud: given only this state, can I evaluate the transition without knowing how I arrived here? If the answer is no, something is missing. In edit distance the state is a pair of prefix lengths $(i,j)$, because how you aligned those prefixes never affects what remains. In knapsack it is the item index and the capacity still free. This is exactly the Markov property, transplanted from probability into algorithm design.

There is one formula, and it covers every dynamic program you will write:

time = (number of states) x (cost of one transition)

Read the table in the other direction and it becomes a design tool. If your state space is $2^n$, no cleverness in the transition will rescue you; the state is what has to change. If the transition costs $O(n)$ inside an $O(n^2)$ state space, that inner minimum is where an optimisation such as a monotone-split or convex-hull trick would pay.

The 0/1 knapsack transition is a two-way choice, and both branches read from the previous row only. That single observation drives two later decisions.

First, the evaluation order: fill rows in increasing $i$ and any cell in row $i$ has what it needs. Second, the space: if nothing ever reads row $i-2$, you do not need to keep it, and the whole table collapses to two rows, or with care to one.

The second option also silently encodes the constraint that makes this the 0/1 knapsack. Item $i$ contributes at most once because the branch that takes it drops to row $i-1$, where item $i$ is no longer available.

Given items with weights and values and a capacity, maximise total value without exceeding capacity:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 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(capacity + 1):
            dp[i][w] = dp[i - 1][w]              # skip
            if wt <= w:                          # take, if it fits
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)
    return dp[n][capacity]

The two loops enumerate the states, the body is the transition, and the loop order is the evaluation order. Nothing in this code is specific to knapsack except the three lines in the middle, which is the point: the shape is reusable, the transition is the problem.

Since every cell reads only row $i-1$, you can drop to a single array. But now the direction of the inner loop carries meaning, and getting it wrong does not produce an error. It produces a different problem's answer.

for i in range(n):
    for w in range(capacity, weights[i] - 1, -1):   # DESCENDING
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

Going downward, dp[w - weights[i]] has not yet been touched this round, so it still holds the row $i-1$ value and item $i$ is used at most once. That is 0/1 knapsack.

Going upward, that same cell was already updated this round, so it may already include item $i$, and the item gets reused freely. That is the unbounded knapsack.

One keystroke separates two different problems, both of which run and return plausible numbers.

The table gives you a number. Usually you want the artefact: which items, which alignment, which split.

Two standard approaches. Store a parent pointer alongside each cell recording which branch won, then follow pointers back from the final state. Or store nothing and re-derive it, walking backwards from $(n, W)$ and asking at each cell whether it equals dp[i-1][w]; if not, item $i$ must have been taken.

This collides directly with the space optimisation. Rolling to one array leaves you the optimum's value and no way to reconstruct it. For sequence alignment the tension is resolved: Hirschberg's algorithm, published in Communications of the ACM in 1975, recovers the full alignment in $O(\min(n,m))$ space and still $O(nm)$ time, by recursively splitting on the middle column and solving each half. You pay a constant factor in time, not an asymptotic one.

The knapsack table has $nW$ cells, so the algorithm is $O(nW)$, and knapsack is NP-hard. Those two statements are both true and do not conflict.

Complexity is measured against the length of the input, in bits. The capacity $W$ is a single number, written in about $\log_2 W$ bits. So a capacity of one billion adds roughly 30 bits of input while multiplying the work by a billion. The running time is exponential in the input length, and $O(nW)$ is called pseudo-polynomial.

The consequence is a sharp performance cliff that has nothing to do with the number of items. Knapsack with 50 items and capacity 1,000 is instant. Fifty items and a capacity of $10^{12}$ is hopeless, even though the input barely grew. Problems like this, NP-hard but pseudo-polynomially solvable, are called weakly NP-hard.

Suppose the knapsack gains one constraint: take at most $k$ items. The natural move is to keep the same table and check the count at the end. That is wrong, and it fails quietly.

The state $(i, w)$ records the best value for a prefix and a capacity, but two different item sets can reach the same cell with the same value and different cardinalities. The recurrence keeps whichever has more value and discards the count, so by the time you check, the information is gone.

The fix is to put the missing quantity into the state: $(i, w, j)$, where $j$ is items used so far. The table grows by a factor of $k$ and the running time with it, which is the honest price of the extra constraint.

The general symptom is worth memorising: a dynamic program whose state is too small does not crash, it lies.