A Dynamic Programming Table Remembers Only What the Future Needs

Start with choices, not dimensions

A dynamic programming table is difficult to invent when we begin by asking how many dimensions it needs. The dimensions and the recurrence depend on each other. We can discover them together instead.

Start with a partial history : the choices made so far. Ask what actions are possible next, what each action changes, and what the final answer must test. Initially, we can keep the entire history. That is enough information, even if it is far too much.

Here is a small decision tree. The strings record choices, not table coordinates.

The tree is the starting point, not the intended implementation. We want to stop copying distinctions that no future decision can use.

Test what can be forgotten

Propose a summary of a history . Before turning it into a table index, test it:

If , can any remaining choice distinguish from in a way that matters to the answer?

For a reachability problem, a useful sufficient test is that the same actions are legal, matching actions produce the same next summary, and the final acceptance test depends only on the summary. For optimisation, also account for how actions change the score.

One counterexample is enough to reject a proposed summary. In bicoloured subset sum, remembering only the processed prefix and sum fails:

Here . The item colours are fixed; the histories selected different items. The missing distinction belongs in the information we retain.

This gives a practical way to discover state: propose a summary, try to break it with two histories, and add the missing information. We need a sufficient summary, not necessarily the smallest possible one.

Equal states replace repeated subtrees

Suppose the summary passes the test. Write . For a legal action , the next summary must be computable without reopening the history:

Two histories with the same state now have the same transitions at the level we care about. Instead of keeping two copies of their future computation, use one state vertex.

Not every history must merge with another. The benefit comes wherever many histories share states. A valid state description can still have exponentially many states; correctness alone does not establish efficiency.

The coordinates and the value do different jobs

A table entry has an address and a payload:

The coordinates describe the situation needed for future decisions. The value combines the histories reaching that situation according to the question we are answering.

Counting assumes the histories are the objects we intend to count, or represent those objects uniquely. Merging state vertices must not silently discard their multiplicities.

Keeping only the best score needs a further justification: every continuation available to a discarded candidate must be reproducible by the retained candidate with an outcome at least as good. For example, at the same processed prefix and exact bag weights, profit dominates profit when future profits are added and the objective is maximisation. This is the relevant mechanism behind Bellman’s principle of optimality.

By contrast, discrepancy does not dominate : a future blue item favours , while a future red item favours . The discrepancy cannot be replaced by its minimum.

Nor must every retained quantity become an array dimension. These two representations preserve the same reachability information:

The first uses a Boolean value and three coordinates. The second uses two coordinates and a set-valued entry. A single minimum discrepancy is not equivalent to either: it throws information away. The information requirement comes before the choice of storage layout.

Read one edge in both directions

Once the state is sufficient, the recurrence is bookkeeping over its edges. We do not need to invent a separate mechanism.

In the graph below, an action from generates . Looking from , the same edge identifies as a predecessor. Two predecessors can contribute to the same destination.

For reachability, reading incoming edges gives

with the starting states supplied separately. For a maximum additive score with edge gain , it gives

Unreachable entries are false for reachability, zero for counting, and for maximum-score optimisation. A zero score is not the same as an unreachable state.

A table is an address system for the graph

If , then are coordinates locating a vertex. The table does not add new mathematical states; it gives the graph’s states an address.

Here is one possible reachability slice at a fixed layer . A dot means false. The arrow is one take transition for a red item of value .

A dense array reserves every coordinate combination. A sparse map stores only encountered states. Memoisation explores states when needed; bottom-up evaluation follows a dependency order. These are ways to evaluate and store the same recurrence, not substitutes for defining a sufficient state.

Layered selection problems have an immediate order: transitions advance . Other dynamic programmes may advance interval length or subset size instead. The dependency order must be justified; a graph with cycles cannot simply be evaluated once in arbitrary order.

Finally, count states and transitions, including the cost of manipulating each value. A set-valued entry is not a constant-size Boolean. Numerical coordinate ranges must be compared with the encoded input length, as in pseudo-polynomial dynamic programming.

The order of discovery is not “dimensions first, recurrence second”. Trace a choice, find what it needs, test what can be forgotten, and choose how to combine the remaining histories. The table records the distinctions that survive that test.