State Sufficiency: What the Past Must Leave Behind

Every DP makes a claim that is easy to state and hard to check: two partial solutions that agree on the recorded state can be completed identically. If the claim is false, the algorithm does not run slowly — it returns the wrong answer, because two genuinely different situations were merged into one cell and the table kept whichever value arrived first. If the claim is true but the state is bloated, the algorithm is correct and unusably large. State design is therefore the point where correctness and cost are decided simultaneously, before any code exists.

The condition has a name borrowed from stochastic processes. A state is sufficient when the future evolution of the computation depends on the past only through the state. The DP literature usually states it as: the optimal value of the remaining problem is a function of the state alone.

The sufficiency test

A workable test is to ask what a completion needs to know. Take a partial solution and imagine two different histories that reach the same proposed state. Enumerate every fact the history establishes that could constrain or reward a continuation. If the two histories disagree on any of those facts, the state is insufficient, and the disagreement must be captured by an additional component.

Consider the problem of computing, for each day, the maximum profit from at most k transactions of one share. A natural first attempt records the day and the number of transactions used: best[d][t]. That state is insufficient, because the continuation differs depending on whether a share is currently held. A history that has used t transactions and holds a share cannot sell before buying again, while one that holds nothing can. The repair is a third component, held ∈ {0, 1}, giving best[d][t][held] and a transition that either holds, buys, sells, or does nothing. The number of states triples, and without the extra bit the table cannot express the constraint at all.

The same test applied to the knapsack problem shows a different kind of choice. Once items have been processed in a fixed order, the state (i, capacity used) is sufficient when the objective is to maximize value subject to a weight cap: two histories that have spent the same capacity on the same prefix have the same set of continuations. The alternative state (i, value_so_far) is sufficient only for a different question — the least weight that achieves a value — and it is far larger when values are large and weights are small. Sufficiency is necessary, not sufficient for a good design; among sufficient states, the smallest wins.

Why the longest-path state must be exponential

The cleanest demonstration that state design is not cosmetic comes from the longest simple path problem, which is NP-hard and whose DP formulation makes the difficulty visible rather than hiding it in a proof.

Define the state as (current vertex, set of vertices already visited). The recurrence is

longest(v, S) = max over neighbours u not in S of ( 1 + longest(u, S ∪ {u}) )

with longest(v, S) = 0 when no unvisited neighbour exists. This is correct: the set S is exactly the information a continuation needs, because the only constraint on a simple path is that vertices not repeat. The table has n · 2^n cells. For n = 30 that is about 3.2×10^10 cells, and even at one byte per cell it exceeds the memory of a single machine.

Now compare with shortest path, where the state is just (vertex). The difference is that shortest paths have optimal substructure without the visited set, because a shortest path never revisits a vertex when edge weights are non-negative — any cycle could be removed to shorten the path. The constraint that forced the extra dimension in the longest-path case is automatically satisfied in the shortest-path case, so recording it is unnecessary. This is the general rule: a state component is needed exactly when the constraint it encodes is not implied by the optimization itself.

Hamiltonian-path-style subset DP is the practical form of this state, and it is treated as a technique in subset DP and the Held-Karp recurrence. Its 2^n factor is not an implementation detail to be optimized away; it is the algorithmic content of an exact solution to an NP-hard problem.

Dimensions that pay for themselves

Adding a dimension multiplies the table, so each one must earn its place. Three patterns recur.

Resource accounting. The dimension records a quantity consumed or produced: capacity in knapsack, transactions in the stock problem, coins in change-making, characters deleted in edit distance when the objective is asymmetric. These dimensions are bounded by a problem parameter and their cost is usually acceptable. When the parameter is a magnitude rather than a count, the result is a pseudo-polynomial bound, discussed in the knapsack capacity state.

Structural position. The dimension records where a decomposition boundary sits: the interval [lo, hi] in matrix-chain multiplication, the two indices in sequence alignment, the subtree root in tree DP. These dimensions are bounded by input size and typically give a table of size n² with O(n) transitions, hence O(n³).

Mode or phase. The dimension records which of a small number of regimes the partial solution is in: holding versus not holding, currently inside a run versus between runs, last character matched versus skipped. These cost a small constant factor and are almost always worth it, because they encode constraints that no amount of value optimization can reconstruct.

The distinction between the first and second kinds matters for complexity claims. A dimension over an input size (n, m) yields a polynomial bound in the input length. A dimension over an input magnitude (W, T, a sum of values) yields a bound polynomial in the numeric value, which is exponential in the number of bits used to write it. The same table shape has a different complexity class depending on which kind of quantity indexes it.

Dominance, and when a state can be dropped

The converse of sufficiency is redundancy. If one state’s set of possible completions contains another’s, and it is never worse, the dominated state can be removed. This is the mechanism behind several of the fastest DP formulations, and it is worth separating from sufficiency because it is optional rather than required for correctness.

In a scheduling DP where the state is (jobs scheduled, time elapsed), two histories with the same job set are comparable: the one that finished earlier dominates, because any schedule feasible from the later one is feasible from the earlier one. Keeping only the Pareto frontier over (time, cost) pairs can reduce the table from a product of ranges to the number of non-dominated points, which is often much smaller. The longest increasing subsequence algorithm with a tails array is the sharpest example: the O(n²) state space (index, last value) is collapsed to a one-dimensional array of best-ending values, which is exactly the Pareto frontier over “smallest tail for each length”. That collapse, and the invariant that justifies it, is the core of the tails-array LIS algorithm.

Dominance requires a proof, and the proof is always an exchange argument: given a completion of the dominated state, show it is also a completion of the dominating one, with no worse objective. Without that argument, pruning is a guess that produces plausible answers on small inputs.

Reconstructing a solution from a state

A state that is sufficient for computing the optimal value is not automatically sufficient for reconstructing an optimal solution. The value table stores numbers; the choices that produced them are gone. Reconstruction needs either a parallel array recording the argmin or argmax at each cell, or a second pass that recomputes which transition attains the stored value.

The second approach is often preferable because it needs no extra memory and cannot go out of sync. Given a filled table, walk from the initial state and at each step test each candidate transition t: if cost(state) == w(t) + cost(next(t)), follow t. Every state is visited once, so the walk costs one transition scan per step of the path, against O(table size) for a pass that recomputes cells in bulk. Ties mean multiple optimal solutions exist, and the walk must follow one consistently; an arbitrary choice among ties is fine, but the value reported must be recomputed along the reconstructed path rather than copied from the table, or an inconsistent choice will produce a path whose cost differs from the stored optimum.

Two practical traps. First, the reconstruction must terminate: if a transition has zero weight and does not change the state, the walk loops forever. Second, if the table was computed with a space-saving technique such as the rolling-array trick, the cells needed for reconstruction were never stored, and reconstruction must either be interleaved with the computation or rerun against a saved decision record. Those techniques are covered in two-dimensional tables for edit distance.

What a state cannot express

Three limits are worth knowing before attempting a state design.

Non-Markovian objectives. An objective that depends on the whole history — the number of distinct values seen, the maximum over all prefixes, the parity of a running count — can be handled only if the relevant summary is finite. “Number of distinct values” needs a set, which is exponential in general. “Maximum over prefixes” needs one number and is cheap. The test is whether the summary has a bounded representation.

Constraints coupling non-adjacent decisions. A constraint like “at most one item from each group” is easy: add a group index and process groups in order. A constraint like “no two chosen items within distance 3 in the original order” needs a window of the last three decisions, which is a state dimension of size 2³. Both are tractable, but the second costs 8× and the generalization to distance k costs 2^k.

Order-dependent costs. If the cost of adding an element depends on the relative order of everything added so far, the state must encode that order. Interval DP sidesteps this by building solutions from the inside out, so the only ordering information needed is which interval is being filled. Recognizing that a problem is an interval problem — that the last operation splits a contiguous range — is often the entire insight, and it is developed in interval DP and split enumeration.

The practical summary: enumerate the facts a continuation can depend on, keep the ones not implied by optimality, prove the kept set sufficient by exhibiting a completion, and then count the product of the dimension sizes to see whether the design is affordable. A state that fails the last step is correct and useless; one that fails the first is fast and wrong.