三個問題，一台機器
你現在已經建好了動態規劃機器的每一個零件。你知道什麼問題適用——最佳子結構加上重疊子問題——也知道讓它運轉的四個步驟：選一個狀態、寫出轉移、挑一個計算順序，以及若你需要的不只是一個數，就重建出真正的解。這篇正是這台機器發揮價值的地方。我們把它跑在三個並非玩具的問題上——它們藏在拼字檢查器、版本控制的差異比對、DNA 比對器與預算規劃裡——而你會看見完全相同的食譜產出三個相當不同的答案。
別把這三個當成要背的事實，而要當成要內化的模式。0/1 背包是經典的「在預算下挑一個子集」問題；最長共同子序列（LCS）與編輯距離是經典的「對齊兩個序列」問題。你日後設計的幾乎每個動態規劃，都會與其中之一押韻。在此要養成的本領，是讀一個新問題時聽出它呼應哪個經典——因為一旦聽出來了，狀態與轉移幾乎是自己寫出來的。
0/1 背包：在預算下挑一個子集
你有 n 個物品；物品 i 的重量是 w_i、價值是 v_i，而袋子最多能裝的總重量是 W。每個物品要嘛整個拿、要嘛留下——那個「0 或 1」就是全部關鍵。你想要裝得下的最有價值子集。為何不貪婪地先抓每單位重量價值最高的？因為那正是貪婪那階的陷阱：對不可分割的物品，貪婪規則可以差到任意程度，因為你削不出一小片去填剩下的空隙。所以我們改在子問題上推理。
這裡有個解鎖它的關鍵動作——選對狀態。令 dp[i][c] 為「只用前 i 個物品、可用容量恰為 c」時的最佳總價值。轉移對物品 i 問一個是非題：要嘛不拿它（價值 dp[i-1][c]），要嘛在裝得下時拿它，獲得 v_i 但花掉 w_i 的容量（價值 v_i + dp[i-1][c - w_i]）。答案是兩者中較大的。那個單一的「拿或不拿」分支，就是每個子集動態規劃的心跳。
dp[i][c] = max(
dp[i-1][c], # skip item i
v[i] + dp[i-1][c - w[i]] # take item i, only if w[i] <= c
)
# base: dp[0][c] = 0 for all c (no items -> no value)
# answer: dp[n][W]由於 dp[i] 只依賴 dp[i-1]，自然的計算順序是 i 從 1 到 n、c 從 0 到 W。表格有 n*(W+1) 格、每格花 O(1)，所以執行時間是 O(n*W)。在那個 W 上停一下：它是容量的「數值」，不是它的位元長度，所以這是偽多項式，而非真正的多項式——把容量加倍，工作量就加倍，即使把這個數字寫下來只多了一位。對不大的 W 它快得令人愉悅；對天文數字般大的 W 則不然，而這個落差絕非偶然，因為 0/1 背包是 NP 困難的，目前並不知道真正多項式時間的精確演算法。
LCS：對齊兩個序列
現在換一個形狀。給定兩個字串 X 與 Y，最長共同子序列是同時出現在兩者中、保持順序但不必連續的最長字元序列。在「ABCBDAB」與「BDCAB」中，「BCAB」是一個長度為 4 的共同子序列。這是檔案差異比對工具背後的引擎：兩個版本共享、且保持順序的行，恰好就是它們的 LCS，而其餘一切都是插入或刪除。注意是子序列、不是子字串——允許有間隙，這正是為何暴力法（試遍 X 的全部 2^m 個子序列）沒指望，而動態規劃不可或缺。
用前綴來定義狀態——這是序列問題最得力的選擇。令 dp[i][j] 為 X 的前 i 個字元與 Y 的前 j 個字元的 LCS 長度。只看最後一個字元。若 X[i] 等於 Y[j]，那個共享字元可以作為某個 LCS 的結尾，所以 dp[i][j] = 1 + dp[i-1][j-1]：把它們配對，並在兩個更短的前綴上遞迴。若它們不同，至少有一個不在 LCS 裡，所以我們丟掉一端、取較好的：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。基底情況是空前綴：dp[0][j] = dp[i][0] = 0。
逐列填表，i 從 1 到 n、j 從 1 到 m；每格只看上方與左方，所以當你抵達一格時，它的三個鄰居都已就緒。代價是 O(n*m) 時間，而若你只要長度，靠保留兩列即可做到 O(min(n,m)) 空間。要還原真正的子序列，從 dp[n][m] 向後走：遇到配對就斜向移動並輸出該字元；否則朝給出最大值的那個鄰居移動。把蒐集到的反轉，你就得到一個最佳 LCS。
編輯距離：LCS 較富有的表親
編輯距離（萊文斯坦距離）問：最少需要幾次單字元編輯——插入、刪除或替換——才能把字串 X 變成字串 Y？「kitten」用三次編輯變成「sitting」（替換 k->s、e->i，插入 g）。這是拼字檢查器提供修正背後、以及生物學序列比對裡的數學。它是 LCS 的表親，因為兩者都比較兩個前綴、並決定對最後字元怎麼處理——但編輯距離是最小化一個成本、而非最大化一個長度，而且它多帶一個 LCS 沒有的動作（替換）。
相同的前綴狀態：令 dp[i][j] 為 X 的前 i 個字元與 Y 的前 j 個字元之間的編輯距離。轉移直接讀出三種編輯。若 X[i] = Y[j]，最後字元已免費相符，所以 dp[i][j] = dp[i-1][j-1]。否則我們付 1，並取三種修補中最便宜的：刪除 X[i]（dp[i-1][j]）、插入 Y[j]（dp[i][j-1]），或替換（dp[i-1][j-1]）。這次基底情況不是零——這是它在精神上與 LCS 唯一不同之處：把一個 i 字元的前綴變成空字串要花 i 次刪除，所以 dp[i][0] = i、dp[0][j] = j。
- 狀態：dp[i][j] = X[1..i] 與 Y[1..j] 之間的編輯距離。
- 基底情況：dp[i][0] = i、dp[0][j] = j（全刪，或全插）。
- 轉移（相符）：若 X[i] = Y[j]，dp[i][j] = dp[i-1][j-1]——零成本。
- 轉移（不符）：否則 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。
- 順序：先 i 後 j、遞增；每格需要它的上、左、左上鄰居，而它們都已填好。
代價是 O(n*m) 時間與 O(n*m) 空間——若你只要那個數並滾動兩列，則為 O(min(n,m)) 空間。要還原實際的編輯序列，不必另存資訊：只要從 dp[n][m] 回溯，檢查三者（或免費相符）中哪一個產生了每個值，這正是你為任何製表動態規劃學過的父指標走訪。注意從 LCS 改動的有多少——不同的目標、多一個動作、非零的基底情況——然而那四步食譜一模一樣。那份相同，正是本階真正的課題。
什麼會延用，什麼要當心
退一步看，這份家族相似令人吃驚。背包以（已用物品數、剩餘容量）作索引、在拿或不拿上分支；LCS 與編輯距離以（X 的前綴、Y 的前綴）作索引、在對最後字元怎麼處理上分支。三者中狀態都是進度計數器構成的元組，轉移都是一個常數大小的小選擇，而表格的填法讓每個依賴在被需要前都已就緒。下次面對陌生的動態規劃時，先問：我的進度計數器是什麼，每一步的小決定又是什麼？那就是選狀態與轉移——那兩個難的部分，正是你上一篇操練過的同樣兩個部分。
在你動用這些之前，三個誠實的提醒。第一，漸進描述的是「縮放」、不是每個尺寸上的判決：O(n*W) 的背包對小的 W 極好，但那個 W 是個數值、不是位元數，所以它只是偽多項式——這提醒我們，同一個 O(n*W) 在某個實例上很快、在另一個上卻沒指望。第二，這些表格大小也決定了你的空間，而那個縮減記憶體的兩列技巧也丟掉了路徑，所以重建需要完整的表，或一個更聰明的（赫希伯格式）分治法。第三，別過度信任這個模式：配對最後字元之所以行得通，是因為這些目標的最佳子結構已被證明，而一個表面相似的問題（譬如禁止間隙的最長共同「子字串」）需要不同的遞迴關係式。食譜是個指引，永遠不是「檢查子結構真的成立」的替代品。