Reconstructing the Solution From a DP Table

What This Concept Is

Reconstruction recovers a feasible object attaining a computed value. Store a choice for each state, or retain the values needed to retrace a winning transition. The returned witness must preserve original identities, order and constraints. Its value must equal the optimum, but feasibility alone does not prove optimality.

Multiple witnesses can be equally good. The default contract here accepts any optimum. Lexicographically smallest output, all optimal objects and the number of distinct optima are separate problems with additional proof obligations.

Why It Matters Here

A planner needs chosen jobs; a text tool needs an alignment; an optimizer needs a parenthesization. A correct number paired with an illegal object is a failed implementation. Independent witness checks localize this failure without duplicating the algorithm under test. They also expose information destroyed by space reduction.

Concrete Examples

0/1 knapsack. With (weight,value) items [(2,3),(3,4),(4,5)] and capacity 5, a prefix-by-capacity table gives value 7. At row i, if D(i,c)=D(i-1,c), skipping item i-1 is valid. Otherwise it must have been used: record its index and reduce c by its weight. In both cases reduce i. The result [0,1] has distinct identities, total weight 5 and value 7. Equality permits skipping even when a different tied optimum takes the item.

Unsafe one-array parents. One item (2,3), capacity 4. Descending updates set value[4]=3 with predecessor capacity 2, then set value[2]=3. Following the mutable capacity pointers now appears to select the same item twice, although the final value[4] is correct. A pointer to a slot is not a pointer to the old version of that slot. Retain layers, immutable predecessor records with honest space accounting, or a justified reconstruction algorithm.

LIS. Tails [2,4,6] after input [3,5,6,2,4] give the right length 3, but those tail values occur in input positions 3,4,2 and are not a subsequence. Remember the input index achieving each tail and the predecessor index chosen when processing each item. Replacements then leave old predecessor chains intact.

Alignment. Return ordered pairs (source character or None, target character or None). Removing gaps from the two columns must recover the original strings. Count one for each unequal pair; (None,None) is forbidden. This avoids ambiguous in-place string indices while still describing executable edits from left to right.

Common Confusion / Misconceptions

Local tie-breaking does not automatically yield a globally lexicographically smallest witness. Summing counts of tied transitions counts distinct objects only if their decompositions are disjoint; repeated edit scripts or equivalent objects can otherwise be counted multiple times. Output storage belongs in a complete space report, even when auxiliary working storage is small.

How To Use It

Define the witness format before optimizing memory. For every backward step, show that the predecessor was valid at the relevant layer and that a rank decreases. Check identities, membership, feasibility and recomputed objective independently. Compare optimum values against exhaustive search on tiny inputs, accepting every valid tie rather than one reference ordering.

Check Yourself

What does a feasible cost-7 selection prove without an upper bound? Why can a capacity pointer become stale? Which extra requirement would make tie-breaking part of correctness rather than presentation?

Mini Drill or Application

For two distinct items both (2,3), capacity 2, list every optimal index list. Feedback: [0] and [1]. [0,1] exceeds capacity; [0,0] repeats an identity. Build checks that accept both valid answers and reject both invalid ones.

Read This Only If Stuck

Skiena: reconstructing the edit-distance path. Follow one small table backward, then read the state and output contracts.