Recurrences as DAGs: Why Optimal Substructure Makes Tables Work

The naive recursive computation of the Fibonacci numbers makes 331,160,281 calls to produce F(40), because the call count satisfies T(n) = T(n−1) + T(n−2) + 1 and equals 2·F(n+1) − 1. The same numbers computed in a table need forty additions. Nothing about the arithmetic changed; what changed is that the second computation visits each distinct subproblem once, while the first visits each one as many times as there are paths to it in the recursion tree.

That gap between “number of paths” and “number of distinct subproblems” is the entire content of dynamic programming. It is worth stating as a graph property, because the graph view makes the design decisions concrete: what the vertices are, which edges exist, whether the graph is acyclic, and in what order to visit it.

A recurrence is a graph, not a function

Take the minimum-coin problem: given denominations and a target T, find the fewest coins summing exactly to T. Write best[s] for the answer at sum s. Then

best[0]   = 0
best[s]   = 1 + min { best[s − c] : c ≤ s }

Read as a graph, each sum from 0 to T is a vertex, and each coin c with c ≤ s contributes a directed edge s → s − c of weight 1. The answer is the shortest path from T to 0, and because every edge strictly decreases the sum, the graph is acyclic and the path length is at most T.

This identification is exact, not an analogy. A DP table is an array of shortest-path distances; a DP transition is a relaxation step; the base cases are the distances of the source vertices. Once the graph exists, three questions follow mechanically. Is it acyclic? If so, a topological order gives an evaluation order in which every vertex is computed after all of its successors. How many vertices are there? That is the size of the table. What is the average out-degree? That is the transition cost per cell, and the product is the running time.

The distinction between the two standard implementations is then only a choice of traversal. Bottom-up tabulation visits vertices in an order the programmer supplies, which must be a topological order. Top-down memoization performs a depth-first search and caches results, which produces a topological order lazily, restricted to vertices actually reachable from the query. The mechanics of that second option, including its costs, are covered in Memoization Mechanics.

What optimal substructure asserts, and what it does not

The textbook condition is that an optimal solution contains optimal solutions to its subproblems. The proof template is cut-and-paste: suppose a globally optimal solution used a suboptimal solution to one of its subproblems; replacing that part with the better one yields a strictly better overall solution, contradicting optimality. This argument is short and it is easy to apply it where it does not hold, because it silently assumes the subproblems are independent.

The longest simple path in a graph is the standard counterexample. Let P be a longest simple path from u to v passing through w. The subpath from u to w is certainly a longest simple path from u to w, and likewise for w to v. Composing the two optimal halves does not give an optimal u-to-v path, because the halves may share vertices; the concatenation is then not simple at all. The subproblems overlap in a way the decomposition did not account for. Adding the set of visited vertices to the state repairs the argument and destroys the polynomial table: the state space becomes 2^n subsets. The cost of that repair, and the point at which it becomes the only correct option, is the subject of State Sufficiency.

So optimal substructure is a claim about a particular decomposition, and the decomposition includes the state. A recurrence is correct when two things hold together: the state captures everything about a partial solution that later decisions can depend on, and the optimal value of the whole is a function of the optimal values of the parts. The first is a modeling property; the second is proved by exchange. Neither implies the other.

Optimal substructure also does not imply that a greedy algorithm works. Greedy needs the stronger greedy-choice property: some optimal solution begins with the locally best choice, so the choice can be committed without enumerating alternatives. Coin systems with denominations 1, 5, 10, 25 have that property; the system 1, 3, 4 does not, and the minimum-coin answer for 6 is two coins (3 + 3) where the greedy choice of 4 leaves 1 + 1 and needs three. The DP does not care about the difference; it enumerates every alternative at each state, which is exactly the cost greedy avoids.

The work is states times transitions

Two counts matter and they are often confused. The number of distinct states is the size of the vertex set. The number of root-to-leaf paths in the recursion tree is what an uncached recursion enumerates, and it can be exponential in the number of states.

For Fibonacci, the state is a single index, so there are n + 1 states, each with two outgoing edges. The uncached recursion explores 2·F(n+1) − 1 calls, a number that grows as φ^n with φ ≈ 1.618. For n = 39 that is the 331,160,281 calls quoted above against 40 states and 39 additions, a ratio above 8×10^6. The ratio is not a constant factor that an optimizing compiler can absorb; it is the difference between a program that finishes and one that does not.

For the coin problem the state count is T + 1 and the out-degree is the number of denominations k, so the total work is O(T·k). This is the first appearance of a pattern that recurs throughout the cluster: the running time is a product of a state-space size and a branching factor, and both are consequences of modeling choices rather than of the input alone. When the state includes a numeric quantity such as a capacity or a sum, the state count is proportional to that quantity’s magnitude rather than to the number of bits used to write it, which is why the resulting bound is called pseudo-polynomial; the knapsack article works through the consequences.

Evaluation order, and what a cycle means

A table can be filled in one pass only if the state graph is acyclic. Cycles indicate one of two things. Either the state is under-specified, so that two states that should be distinct have been merged, or the problem is genuinely a fixed-point computation and requires iteration rather than a single pass. Single-source shortest paths with negative edge weights are the canonical second case: the recurrence d[v] = min over edges (u,v) of d[u] + w(u,v) refers to itself, and the standard resolution is to relax edges repeatedly until no distance improves.

The direction of the recurrence is a free choice that changes which states are reachable and which must be initialized. Backward DP starts from the answer state and recurses toward base cases; forward DP starts from base cases and pushes contributions into larger states. For the coin problem, backward DP from T touches only sums that are reachable by subtracting denominations, while forward DP over all 0..T touches every sum, including those that cannot be formed. When the reachable subset is much smaller than the full range, the backward direction can be dramatically cheaper, and when the recursion is deep, the forward direction avoids stack growth.

def min_coins(coins, target):
    INF = float('inf')
    best = [0] + [INF] * target          # best[s] = fewest coins summing exactly to s
    for s in range(1, target + 1):       # sums increase, so dependencies are ready
        for c in coins:
            if c <= s and best[s - c] + 1 < best[s]:
                best[s] = best[s - c] + 1
    return best[target] if best[target] != INF else -1

The loop over s is a topological order of the state graph read backwards: when best[s] is computed, every best[s − c] has already been finalized because s − c < s. The sentinel matters: the comparison best[s − c] + 1 < best[s] adds one to a cell that may still hold “unreachable”, so INF must stay distinguishable from an ordinary answer once incremented. With float('inf') the sum is still infinite and the test is false, which is why an unreachable predecessor never produces a spurious improvement. In a fixed-width integer table the same pattern overflows unless the infinity is kept below the type’s maximum by at least one, and -1 must be distinguishable from a legitimate answer of zero, which occurs whenever the target is zero.

Failure modes that survive a correct recurrence

Four mistakes recur even when the recurrence itself is right.

Double counting. In a maximization or minimization, taking the best over predecessors is safe because each state holds one value and ties collapse. In a counting DP, two different transition orders can produce the same combinatorial object, and the count is then too large. Counting paths in a DAG is safe because each path has exactly one last edge; counting subsets by iterating elements is safe because each element is decided once. Counting structures whose decomposition is not unique is not safe without a canonical rule for which decomposition is counted.

Unreachable states treated as zero. A zero-initialized table asserts that every state is reachable at cost zero. For maximization problems this silently invents solutions. Initialization must encode “no solution” distinctly, and every transition must propagate it.

Ties and reconstruction. When several transitions achieve the optimum, the table stores the value but not which one produced it. Reconstruction needs a parallel array of choices, and the choice recorded must be the one consistent with the value stored, or the reconstructed solution will not match the reported cost.

State explosion by one dimension. Adding a dimension to the state multiplies the table size by the size of that dimension. A three-dimensional table over n = 1000 is 10^9 cells, which is 4 GB at four bytes per cell, well past what fits in memory on ordinary machines. The bound is arithmetic, not hardware-dependent: any state design has to be justified against the largest input the program accepts.

The graph framing pays off precisely here. Designing a DP is choosing a vertex set and an edge relation; proving it correct is showing that the vertex set is sufficient and that the edges compose optimally; and estimating its cost is counting vertices and edges. Everything else, including whether the code is recursive or iterative, is an implementation detail layered on top.