Dynamic programming, in depth: states, recurrences, evaluation order and the bugs that break them

When a problem is a DP problem

Two properties must hold. Optimal substructure: an optimal solution to the whole problem can be assembled from optimal solutions to smaller instances of the same problem. Overlapping subproblems: a naive recursion asks for the same smaller instance many times. The first property makes the recurrence correct; the second makes caching worthwhile.

Fibonacci is the smallest illustration of the second property. The naive recursion below computes fib(n-2) once directly and again inside fib(n-1), and the duplication compounds at every level, so the number of calls grows exponentially even though there are only n + 1 distinct arguments.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # fib(n-2) is recomputed inside fib(n-1): O(phi^n) calls

Optimal substructure fails more often than people expect. The longest simple path in a general graph has no clean substructure: the best path from A to C through B cannot be built from the best path A to B and the best path B to C, because those two may share vertices. Shortest paths without negative cycles do have it, which is why Bellman-Ford can be written as a DP over the number of edges used. If you cannot argue substructure in one or two sentences, the recurrence you are about to write is probably wrong.

The subproblem DAG

Every DP has a hidden graph. Each node is a state (a subproblem); each edge points from a state to a state it depends on. For DP to work this graph must be acyclic, because a cycle would mean a subproblem depends on itself. Computing the answer is then a walk over the DAG in reverse topological order, so every dependency is ready before it is needed.

This view explains the cost model directly. Time is the number of states multiplied by the work done per state (the out-degree of each node plus any combining). Memory is the number of states you must keep alive at once. Almost every optimisation in DP either shrinks the state space, reduces per-state work, or discards states that no remaining node depends on.

The recipe: state, recurrence, base cases, order

1. Define the state in words. Write a sentence of the form "best(i, c) is the maximum value achievable using only the first i items with capacity c". If you cannot write this sentence, you do not yet have a state. The state must carry every piece of information the future decisions need, and nothing more; extra dimensions multiply cost.

2. Write the recurrence by considering the last decision. For item i-1 there are two choices: skip it, giving best(i-1, c), or take it if it fits, giving best(i-1, c-w) + v. The state's value is the best of the legal choices. Enumerating the choices at one step, and nothing else, is what keeps recurrences readable.

3. Fix the base cases. best(0, c) = 0 (no items) and best(i, 0) = 0 (no room). Base cases are where most off-by-one bugs live, so write them before the loops.

4. Choose an evaluation order. Either recurse and cache (memoization, top-down), or fill a table in an order that respects the DAG (tabulation, bottom-up). 5. Extract the answer, which may be a single cell, the maximum over a row, or a path through the table.

Top-down: memoization

Memoization is the recurrence written literally, with a cache in front of it. It evaluates only the states reachable from the question actually asked, which matters when the state space is large but sparse.

from functools import lru_cache

def knapsack_topdown(weights, values, capacity):
    n = len(weights)

    @lru_cache(maxsize=None)
    def best(i, c):                     # best value from items 0..i-1 within capacity c
        if i == 0 or c == 0:
            return 0
        w, v = weights[i - 1], values[i - 1]
        skip = best(i - 1, c)
        if w > c:
            return skip
        return max(skip, best(i - 1, c - w) + v)

    return best(n, capacity)

Its costs are real. Each state costs a function call and a hash lookup, so constant factors are several times higher than a tight loop. In CPython the default recursion limit is about 1,000 frames, so a recursion depth proportional to n will raise RecursionError for large inputs; raising the limit trades that for a risk of crashing the interpreter's C stack. lru_cache also requires hashable arguments, so passing a list fails, and a cache defined at module level keeps every entry alive until you call cache_clear().

Bottom-up: tabulation, worked by hand

Tabulation turns the evaluation order into loops. For knapsack, row i depends only on row i-1, so filling rows top to bottom is a valid topological order. Take four items with (weight, value) A = (1, 1), B = (3, 4), C = (4, 5), D = (5, 7) and capacity 7.

Check one cell. In the C row at c = 7: skipping C gives 5 (the cell above); taking C leaves capacity 3, where the previous row holds 4, so 4 + 5 = 9. The maximum is 9. In the D row at c = 7, taking D leaves capacity 2 worth 1, so 1 + 7 = 8, which loses to 9. The answer is 9.

To recover the items, walk back from the bottom-right cell. At row D, 9 equals the cell above, so D was not taken. At row C, 9 differs from 5 above, so C was taken and capacity drops to 3. At row B, 4 differs from 1 above, so B was taken and capacity drops to 0. The chosen set is {B, C}: weight 7, value 9.

def knapsack_table(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]   # row 0 = no items = base case
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
    # Reconstruction: walk back from (n, capacity); a change between rows means "taken".
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    return dp[n][capacity], chosen[::-1]

Choosing between the two

A practical workflow is to write the memoized version first because it mirrors the recurrence, test it on small inputs against brute force, then convert it to a table once it is correct.

Cutting memory with rolling arrays

If a row depends only on the previous row, you need two rows, and often one. The single-array knapsack below is the most common place DP code goes subtly wrong: the direction of the inner loop decides which problem you are solving.

def knapsack_01_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):      # DOWNWARD: dp[c - w] is still last row's value
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

def knapsack_unbounded_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(w, capacity + 1):          # UPWARD: dp[c - w] may already include this item
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Iterating capacity downward means dp[c - w] still holds the value from before this item was considered, so each item is used at most once (0/1). Iterating upward means dp[c - w] may already include this item, so it can be reused without limit (unbounded knapsack, coin change). Both versions pass a test where every item is used once, so write a test where reuse would change the answer.

The price of rolling arrays is that the table needed for reconstruction is gone. Options are to store a compact decision bit per state (one bit per cell instead of a full integer), to recompute, or, for two-sequence problems such as LCS, to use Hirschberg's divide-and-conquer, which recovers the alignment in linear space for about twice the time.

Complexity, and the pseudo-polynomial trap

Knapsack's table is O(n * C), which looks polynomial. It is not polynomial in the input size, because C is written in about log₂ C bits: doubling the number of bits squares the table. Algorithms like this are called pseudo-polynomial, and they are why 0/1 knapsack is NP-hard yet solvable in practice when capacities are small. If weights are large (say, bytes up to 10⁹), swap the roles: index the table by value and store the minimum weight, or use a different method entirely.

Some state spaces are exponential by design. Travelling salesman over subsets has 2n * n states, so exact bitmask DP is practical only up to roughly 20 cities; the travelling salesman DP article works through that case. Use the Big-O guide to sanity-check whether a states-times-transitions estimate fits your time budget before you write code.

Recognising the families

Interval DP has an ordering constraint worth remembering: a range depends on shorter ranges, so the outer loop runs over length, not over the left endpoint. The longest palindromic subsequence article shows that fill order in detail.

Failure modes

• State missing information. The recurrence silently allows illegal moves, for example forgetting a "holding stock" flag. Symptom: answers larger than brute force on small cases.
• Wrong loop direction after space reduction. 0/1 turns into unbounded or the reverse, as shown above.
• Base cases off by one. Using dp[0] to mean both "empty prefix" and "first element". Size tables at n + 1 and keep index 0 as the empty case.
• Fill order that violates the DAG. A cell reads a neighbour that has not been computed and gets 0. Interval problems are the usual victim.
• Overflow in counting DPs. Counting problems grow exponentially; apply the required modulus at every addition in fixed-width languages.
• Recursion limits and unbounded caches in memoized code, covered above.

What to do next

1. Take a problem you solved by pattern-matching and write its state as one sentence, its recurrence as a list of choices, and its base cases.
2. Implement it memoized, then tabulated, and compare both against a brute-force solver on a few hundred random small inputs.
3. Count states and transitions and estimate run time before scaling the input.
4. Apply a rolling array, then write a test that fails if the loop direction is wrong.
5. Add reconstruction and assert that the recovered choices reproduce the optimal value.
6. Work one problem from each family in the table, starting with an interval DP and a bitmask DP.