parent-pointer reconstruction

When you want not just the optimal value but the optimal solution itself, one tidy technique is to leave a trail of breadcrumbs while you fill the table. Every time the transition picks a winning branch for a state, you also write down, in a parallel table, which choice won — which predecessor state or which decision gave the best value. Those recorded choices are the parent pointers, and afterward you recover the solution by simply following the trail from the final state back to a base case, reading off the choices as you go.

Mechanically, alongside dp[state] you keep choice[state]. When you compute dp[state] = best over options of (cost(option) + dp[next(option)]), you store choice[state] = the option that achieved the best. Reconstruction then starts at the goal state, looks up choice[goal], records or applies that decision, moves to the predecessor it names, and repeats until a base case. For longest increasing subsequence done in O(n^2), you keep prev[i] = the index j < i that the best subsequence ending at i extended; starting from the index with the largest dp value and following prev backward, then reversing, yields the actual increasing subsequence, not merely its length.

Parent pointers cost one extra table (the same size as your DP, so the same asymptotic memory) but make reconstruction trivial and fast: the traceback is one pass along a single chain, O(path length), with no re-examination of the transition needed. The alternative — recomputing which branch won by inspecting the value table during traceback — saves that extra table but requires the value table to be fully intact and the transition to be re-evaluated at each step. Either way, the same caveat applies: if you compressed the DP to save memory and overwrote the information the pointers (or the value table) need, you can no longer trace back.