重建最佳解

依前述方式填好的動態規劃，告訴你的是最佳值——最長共同子序列的長度、最少的硬幣數、背包的最大價值。但你往往想要那個東西本身，而不只是它的分數：是哪些字母組成了那個子序列、該交出哪些硬幣、該裝進哪些物品。從填好的動態規劃表中還原出那個真正的最佳物件，就稱為重建，它是表填滿之後另做的一個步驟。

有兩種標準做法。第一種不存任何額外資訊，而是藉由倒著走過填好的表來重新推導出那些選擇：在每一格你問「轉移的哪一支產生了這個值？」然後走到產生它的那個前驅。以編輯距離為例，你從 dp[m][n] 出發，在每一格檢查這個值來自配對（往對角移動，不記錄編輯）、刪除、插入，還是替換（記下該編輯並相應移動），一直走到角落為止；你記下的編輯反轉過來，就是最佳的編輯序列。這在動態規劃之上只花路徑的長度，通常是 O(m + n) 或 O(n)。

第二種做法是在填動態規劃的同時，把獲勝的選擇記在一張獨立的父指標表中，然後就只是從最終狀態順著那些指標回溯。兩種方法都還原出一個最佳解；若有多個解並列最佳，你得到哪一個取決於轉移如何打破平手（例如偏好「跳過」勝於「拿取」，或索引較小者優先）。一個微妙但重要的點：重建需要值表（或父指標）完好無缺，所以那些丟掉舊列的省記憶體技巧——例如把最長共同子序列的表縮成兩列——會摧毀你回溯的能力，你必須保留整張表，或改用像赫希伯格法這類分治式重建，在線性空間內還原路徑。