reconstructing the optimal solution

A dynamic program filled out as described tells you the value of the optimum — the length of the longest common subsequence, the minimum number of coins, the maximum knapsack value. But often you want the thing itself, not just its score: which letters form the subsequence, which coins to hand over, which items to pack. Recovering that actual optimal object from a completed DP table is called reconstruction, and it is a separate step you do after the table is full.

There are two standard ways. The first stores no extra information and instead re-derives the choices by walking the finished table backward: at each cell you ask 'which branch of the transition produced this value?' and step to the predecessor that did. For edit distance, you start at dp[m][n] and at each cell check whether the value came from a match (move diagonally, no edit recorded), a deletion, an insertion, or a substitution (record that edit and move accordingly), continuing until you reach the corner; the edits you logged, reversed, are the optimal edit sequence. This costs only the length of the path, typically O(m + n) or O(n), on top of the DP.

The second way records the winning choice in a separate parent-pointer table as you fill the DP, then simply follows those pointers back from the final state. Both methods recover one optimal solution; if several solutions tie for optimal, the one you get depends on how ties are broken in the transition (for instance, preferring 'skip' over 'take', or lower index first). A subtle but important point: reconstruction needs the value table (or the parent pointers) to be intact, so memory-saving tricks that throw away old rows — like reducing an LCS table to two rows — destroy your ability to trace back, and you must either keep the full table or use a divide-and-conquer reconstruction such as Hirschberg's method to recover the path in linear space.