父指標重建（parent-pointer reconstruction）

當你要的不只是最佳值，而是最佳解本身時，有一個俐落的技巧：在填表的同時留下一串麵包屑。每當轉移為某狀態選出一個獲勝的分支，你也在一張平行的表中記下是哪個選擇贏了——是哪個前驅狀態，或哪個決策給出了最佳值。那些記下的選擇就是父指標，事後你只需從最終狀態順著這串痕跡回溯到某個基底情況，一路把選擇讀出來，就還原了解。

在機制上，你在 dp[state] 旁邊保留 choice[state]。當你計算 dp[state] = 在各選項中取 (cost(選項) + dp[next(選項)]) 的最佳值時，你把 choice[state] 存成達成最佳的那個選項。重建於是從目標狀態開始，查 choice[goal]，記下或套用那個決策，移到它指名的前驅，重複到某個基底情況為止。對以 O(n^2) 做的最長遞增子序列，你保留 prev[i] = 「以 i 結尾的最佳子序列所延伸的那個 j < i」的索引；從 dp 值最大的索引出發、順著 prev 往回走、再反轉，就得到真正的遞增子序列，而不只是它的長度。

父指標花掉一張額外的表（與你的動態規劃同樣大小，所以漸進記憶體相同），卻使重建變得既簡單又快：回溯是沿單一鏈走一遍，O(路徑長度)，無需重新檢視轉移。另一種做法——在回溯時藉由檢查值表來重算哪一支贏了——省下那張額外的表，但要求值表完整無缺，且每一步都要重新評估轉移。無論哪種，同一個警告都適用：若你為省記憶體把動態規劃壓縮、覆寫掉了指標（或值表）所需的資訊，你就再也無法回溯了。