動態規劃的計算順序

在由下而上的動態規劃裡，你一格一格地填表，有一條規則你絕不能破壞：在你計算某一格之前，它所依賴的每一格都必須已經持有其最終值。計算順序就是你造訪各格的次序，選定它以使這條規則始終成立。這是「在打好的地基上一磚一磚砌牆」和「想在半空中放磚」之間的差別——順序搞錯，你就會從一個還沒填的格子讀到垃圾。

把各狀態想成圖中的節點，每當計算 X 需要 Y 時，就從狀態 X 拉一個箭頭到 Y。一個有效的計算順序就是這張相依圖的任一拓樸順序：每個狀態都排在它所指向的全部狀態之後。對於 dp[i] 只依賴較小索引的一維動態規劃，順序就是 i 遞增。對於 dp[i][j] 依賴 dp[i-1][*] 與 dp[i][j-1] 的二維格點動態規劃，逐列由上而下、列內由左而右地填即可，因為這兩個前驅屆時都已完成。對於 dp[l][r] 依賴 [l, r] 內較短區間的區間動態規劃，你依區間長度遞增來迭代，使所有較短區間都已備妥。相依結構決定了順序；你從轉移把它讀出來。

由上而下的記憶化完全繞開了這件事：遞迴自然會在需要某狀態的那個狀態之前先算好相依，所以呼叫堆疊免費地發現了一個有效順序——這是新手覺得記憶化較寬容的原因之一。由下而上逼你把順序寫明，這既是負擔也是好處：正是這個明確的順序讓你能證明規則成立、能藉由丟棄再也不會讀到的格子來壓縮記憶體，而且最關鍵的是，它只有在相依圖無環時才行得通。若狀態 A 需要 B、B 又需要 A，就不存在任何順序，這個表述就壞了——這是你必須重新定義狀態的徵兆。