難的一直都是那條遞迴
前三篇導覽教的是機制。你看到一個直白的遞迴會把同一份工作以指數量級重複，你用一層快取把它包起來得到由上而下的記憶化，又把同一條遞迴改寫成迴圈得到由下而上的製表。但請注意，這三篇導覽都悄悄把遞迴直接交到你手上，從沒說它是從哪來的。本篇要填的正是這個缺口：每個動態規劃的成敗都繫於一條你必須親手發明的遞迴，而發明它就是兩個決定——子問題是什麼（狀態），以及子問題如何相連（轉移）。
好消息和警告在這裡一起出現。狀態一旦選得好，轉移通常自己就寫出來了，而選記憶化還是製表只是工程上的小細節。但若狀態選錯了，再聰明的程式碼也救不了你——你會又快又自信地算出錯誤答案。所以動態規劃真正的功夫不在於把表格寫出來，而在於寫任何程式碼之前、在紙上完成的那個設計步驟。把狀態想成一格表格所回答的精確問題，把轉移想成那句「用較小的答案建出這個答案」的話。
狀態：為單一子問題取的名字
定義狀態的意思，是選出一小束數值，精確地釘住恰好一個子問題，並作為查表的鍵。好的狀態要在兩條互相拉扯的軸上接受檢驗。它必須充分：它得捕捉情境中一切會影響未來的資訊，使得最佳的後續只依賴於狀態，而絕不依賴隱藏的歷史。它也應該最小：不攜帶任何未來會忽略的細節，因為每多一個維度都會讓狀態數倍增——而狀態數就是你必須填的格子數。
充分性的檢驗很具體：站在一個做到一半的解上，只看狀態，問自己手上的資訊夠不夠把下一步選到最佳。如果你發現自己伸手去拿狀態沒記下的事實——先前拿了哪幾件、目前的奇偶為何——那麼狀態就定義不足，相異子問題正擠在同一格裡，答案會出錯。解方絕不是用旁路資料把那個事實偷渡進來，而是把狀態加寬到記下未來所需。以最長遞增子序列為例，弱狀態「前 i 個元素」會失敗，因為轉移無法判斷元素 i 能否延伸某個子序列；修法是 dp[i] =恰以索引 i 結尾的最長遞增子序列，它固定了最後一個元素，使未來只依賴於狀態。
轉移：狀態如何相連
一旦你知道狀態是什麼，轉移就是那條由較小狀態的答案算出某狀態答案的規則。如果說狀態是你儲存的名詞，轉移就是把它們連起來的動詞。它幾乎總是同一個形狀：要解這個狀態，列舉每一個可能的第一步選擇，解出每個選擇留下的剩餘子問題，再加以組合——取最大、最小、求和或計數，端看你在最佳化什麼。把轉移寫對，恰恰就是把遞迴關係式寫對，而它的正確性建立在最佳子結構上：你所引用的每一支都必須本身是一個最佳子答案，否則整件事就錯了。
0/1 背包問題是「第一步選擇」這個形狀最乾淨的示範。以狀態 dp[i][w] =「在容量 w 下使用前 i 件物品的最佳價值」來說，對物品 i 唯一的選擇就是拿或不拿，而轉移直接把這個選擇讀出來。把遞迴念出聲，它就會自己說出故事：用前 i 件物品你能做到的最好，是「忽略物品 i（於是前 i-1 件仍有全部 w 可用）」與「拿取它（賺到它的價值卻花掉它的重量，剩 w - weight[i] 給其餘）」兩者中較好的那個。每一支都是一個嚴格更小狀態的最佳答案——把子結構化為具體。
dp[i][w] = max( dp[i-1][w], # leave item i
value[i] + dp[i-1][w - weight[i]] ) # take item i (needs weight[i] <= w)
# state count * work-per-state = running time
# knapsack: O(nW) states * O(1) work = O(nW)
# LIS (loop over predecessors): O(n) states * O(n) work = O(n^2)轉移也決定了你動態規劃的成本，這值得內化成一條公式：執行時間 =（相異狀態的個數）乘以（計算一次轉移的工作量）。背包的轉移在 O(nW) 個狀態上各做 O(1) 工作，所以是 O(nW)。最長遞增子序列的轉移每個狀態要遍歷 O(n) 個前驅、橫跨 n 個狀態，所以是 O(n^2)。光憑這個乘積，你就能在寫下任何一行之前預測一個動態規劃的複雜度——這也是為什麼縮小狀態能賺兩次，一次省記憶體、一次省時間。
基底情況，以及你填它們的順序
轉移由較小狀態建出較大狀態，但你不能無止境地往下建——你終會碰到下方一無所依的最小狀態。那些就是基底情況，你得在任何迴圈或遞迴跑起來之前，依問題的意義親手直接填好它們。它們是整張表所倚靠的地基；某個基底情況一旦錯了，建在它上方的每個值都會無聲地繼承這個錯誤。它們看起來無關緊要，卻恰恰是最常見臭蟲藏身之處。對空輸入，答案可能是 0（與空字串的最長共同子序列是空的）、或 i（把長度 i 的字串變成空字串要花 i 次刪除）、或 1（在計數型動態規劃裡，「什麼都不做」恰好有一種方式）。
基底情況也編碼了可行性的邊界。當某些情境不可能發生時，你用一個哨兵值替它們播種——求最小時用正無窮大、求最大時用負無窮大——好讓「取最佳」的運算自動繞開它們。硬幣找零是經典例子：dp[0] = 0（零枚硬幣湊出金額零），而每個正金額起始為無窮大，於是一個真正湊不出的金額會維持無窮大，永不被誤認為可達。若改用 0 而非無窮大去播種，不可能的狀態就會偽裝成免費，毒害上方的一切。邊界上的哨兵值錯誤或差一，是藏得最好的臭蟲，因為表的絕大部分看起來都完全合理。
現在你需要一個填格子的順序，而有一條規則你絕不能破壞：在你計算某一格之前，它所依賴的每一格都必須已持有其最終值。計算順序就是任何尊重這條規則的次序。把每個狀態想成一個節點，每當計算 X 需要 Y 時就從 X 拉一個箭頭到 Y；有效的填表順序就是這張相依圖的任一拓樸順序。對 dp[i] 只需較小索引的一維動態規劃，讓 i 遞增即可。對 dp[i][j] 要讀上方、左方、左上方的格點動態規劃，逐列由上而下、列內由左而右地填。對區間型動態規劃，讓區間長度遞增，使所有較短區間先備妥。順序你直接從轉移讀出來。
把答案讀回來
填好的表告訴你最佳解的「數值」——最佳背包價值、最長共同子序列長度、最小編輯成本。但你往往想要最佳解「本身」：要裝哪些物品、哪些字母對齊、要施作哪些編輯。那就是重建解，而光有數值並不會把它交給你。標準技巧是從最終那格沿表往回走，每一步問：轉移的哪一支實際達成了所存的最佳值。你走過的那一支告訴你當初做的選擇；你順著它走到它來自的狀態，重複此事直到抵達基底情況。
- 從持有最終答案的那格開始——對 0/1 背包，就是 dp[n][W]。
- 問是哪一支轉移產生了這個值。若 dp[i][w] 等於 dp[i-1][w]，物品 i 被略過了；否則它被拿了。
- 記下這個選擇（例如「拿了物品 i」），再移到那一支所來自的前驅狀態。
- 重複直到碰上基底情況；把記下的選擇反轉，就是那個最佳解。
靠比較重新推出被選中的那一支是可行的，但更乾淨也更快的習慣是父指標回溯：在你填每一格、選定獲勝那一支的當下，存一個指回它所選前驅的反向指標。如此重建就只是從最終那格沿指標追到基底情況——不必重新檢查轉移，也沒有回程時把平手以不同方式打破的風險。代價是多一個與表同大小的陣列，只要你需要的是那個見證而不只是它的分數，這就是划算的交換。
五問食譜
把這些拼起來，你這輩子寫的每個動態規劃都在依序回答同樣的五個問題。狀態是什麼——子問題那個最小又充分的名字？轉移是什麼——每個狀態的答案如何藉由列舉第一步選擇，從較小狀態得來？基底情況是什麼——那些最小的狀態，親手填好、配上正確的哨兵值？計算順序是什麼——相依圖的一個拓樸順序（或者乾脆遞迴加記憶化，讓堆疊去找一個）？最後，你需要重建解，還是數值就夠了？
在下一篇把這些變成完整的工作範例之前，有兩個誠實的提醒。第一，這整份食譜唯有在問題確實具備最佳子結構時，才會產出正確的程式——轉移「看起來對」從來不是證明，而一條引用了暗中互相干擾之子問題（共用一項狀態未追蹤的資源）的遞迴，無論讀起來多合理都是錯的。第二，這份食譜能預測成本，卻不保證好成本：若你的狀態需要指數量級的值，狀態數乘以每狀態工作量仍可能是指數的，而這正是當一個問題確實看似得把一個子集當作狀態的一部分時所發生的事。動態規劃是一門設計紀律，不是魔杖。