當狀態對了，轉移卻太慢
到這裡，你已經能讀懂一個問題、為它的進度計數器命名，並寫出轉移。但一個正確的動態規劃仍可能太慢，而罪魁禍首幾乎總是同一個：表格的格子數量合理，然而「計算一格」卻要掃過一整段先前的格子。若有 n 個狀態、每格填入要做 O(n) 的工作，你就付出 O(n^2)——n 在幾千時還行，過了十萬就難受了。解法很少是換新狀態；而是讓每次轉移更便宜，靠的是「不重做你已經做過的工作」。這篇收集的正是為此而生的標準工具，也就是本階開頭承諾的加速工具箱。
從頭到尾請記住一個誠實的提醒。大O符號隱藏了常數與低階項，所以一個 O(n log n) 的加速描述的是成本如何「縮放」，而不是保證它在每個尺寸都贏。那個更樸素的 O(n^2) 迴圈，憑著它微小的常數與友善的記憶體存取，在小的 n（有時是大得出乎意料的 n）上可以勝過聰明的 O(n log n) 方法。所以動用機器之前先量測：這些技巧只在 n 真的很大、或轉移真的是瓶頸時才值回票價，而不是一種反射動作。
前綴和：付一次，回答很多次
最謙卑的加速也是最常見的。假設某個轉移需要陣列在某段範圍上的值總和，譬如 dp[i] 對許多 l 的選擇依賴於（a[l..i] 的總和）。每次都從頭重算每個總和，是每次查詢 O(範圍長度)。改成先建一個前綴和陣列：P[0] = 0、P[k] = P[k-1] + a[k]。如今任何範圍 a[l..r] 的總和就只是 P[r] - P[l-1]，一次減法、O(1)。你預先花了 O(n)，讓之後數以千計的範圍提問每次只花常數。這就是前綴和加速最乾淨的情形：預先算好累積的工作量，然後以 O(1) 回答各個窗口。
P[0] = 0 for k = 1..n: P[k] = P[k-1] + a[k] # O(n) once range_sum(l, r) = P[r] - P[l-1] # O(1) each query
這個模式遠不只用於單純的總和。計數動態規劃常需要「有多少種方式落在窗口 [l, r]？」，那是計數表上的前綴和；期望值動態規劃需要範圍平均，那是前綴和除以長度。在像矩陣鏈這類本階前面的區間動態規劃問題裡，合併一段範圍 a[i..j] 的代價常常是 P[j] - P[i-1] 的某個固定函數，於是前綴和讓那 O(n^2) 個區間的每一個都能在不重新掃描的情況下為它的切點定價。心智動作永遠相同：發現一個被許多重疊範圍反覆詢問的量，然後只為它付一次錢。
凸包技巧：本質是直線的轉移
現在來一個對非常常見形狀的更深想法。許多動態規劃的轉移長成這樣：dp[i] = 對所有 j < i 取 ( dp[j] + b[j] * x[i] + c[i] ) 的最小值。把 i 固定，看 min 裡面那部分：對每個較早的 j 它是 dp[j] + b[j] * x[i]，把它當成查詢值 x[i] 的函數，就是一條直線——斜率 b[j]、截距 dp[j]。所以填第 i 格在問：在一組直線中，哪一條在 x = x[i] 這一點上最低？用掃過所有 j 來算 dp[i]，是每格 O(n)、整體 O(n^2)。凸包技巧回答那個「某點上最低的直線」查詢的速度要快得多。
為何會冒出一個凸包，原因在此。取所有直線的下包絡——在每個 x 處，任何直線能達到的最小 y。一條在任何地方都不是最小值的直線（它在整段範圍上都落在某兩條的某種組合之上）可以永遠丟掉；它永遠贏不了任何查詢。存活下來、按斜率排序的那些直線，其包絡形成一條分段線性的凸曲線——正是計算幾何裡那個下凸包的形狀，只是如今活在（斜率、截距）空間、而非（x, y）空間。只有凸包上的直線要緊，而它們是排好序的，於是查詢從掃描變成了搜尋。
- 把轉移 dp[j] + b[j] * x[i] 讀成一條直線：斜率 b[j]、截距 dp[j]；查詢點是 x[i]。
- 維護目前為止所有直線的下包絡（凸包），只保留在某處勝出的直線。
- 加入新直線時，彈掉那些現在被新來者弄成多餘的凸包直線——每條直線只加入一次、至多移除一次。
- 要算 dp[i]，就向凸包查詢 x = x[i] 處最低的直線——用二分搜尋，或當查詢已排序時用一個移動指標。
成本取決於輸入有多溫馴。在最友善的情形——斜率 b[j] 以排好序的順序加入、查詢點 x[i] 也排好序——整個包絡用兩個單調指標維護，每條直線至多被推入與彈出一次，總計是 O(n)。那個彈出論證是貨真價實的攤還分析：單次插入可能移除許多直線，但縱觀整段執行，沒有任何直線能被移除超過一次，所以縱貫整個序列的平均是 O(1)——即使某一個別步驟並非如此。若斜率或查詢以任意順序到來，你就把凸包放進一個平衡結構、對每個查詢做二分搜尋，得到 O(n log n)；李超樹是個乾淨的替代品，能直接處理任意的直線與查詢。
為轉移分批處理的其他辦法
凸包技巧是一個家族的一員：這些方法利用轉移中隱藏的結構，使得某個狀態的最佳切點有助於為下一個狀態定位它。分治法動態規劃最佳化適用於最佳切點索引是「單調」的時候——隨著狀態增長，它的最佳選擇從不往回走。若恆有 opt(i) <= opt(i+1)，你就能以分治的順序解這些狀態，先算中間狀態的最佳值，再用它來縮小兩半的搜尋區間。這把每一層的成本從 O(n^2) 壓成 O(n log n)。代價是對前提條件要誠實：你必須真的擁有單調的最佳值，否則分治最佳化就是錯的。
一個近親主宰著區間動態規劃。當合併成本滿足四邊形不等式時——一種「凹性」，說的是較寬的區間切起來不會比嵌在其中的較窄區間更便宜——最佳切點在兩個區間端點上都是單調的，而Knuth-Yao 加速把一整個區間動態規劃從 O(n^3) 削到 O(n^2)。這正是最佳二元搜尋樹那個動態規劃背後的結構。這三件工具共通的課題在於辨識：問問你的轉移是一個範圍總和（前綴和）、一群直線上的最小值（凸包或李超樹），還是一個帶單調最佳值的搜尋（分治或 Knuth-Yao）。辨識出可分批的形狀就是全部本領；一旦你為它命了名，實作便水到渠成。
加速工具箱的誠實侷限
這些技巧沒有一個會改變動態規劃「算什麼」——它們只是算得更快，而且只在轉移有對的形狀時才行。凸包技巧需要轉移對查詢變數是線性的；把那條直線彎成曲線，凸包論證就垮了。分治與 Knuth-Yao 需要真正單調的最佳值、或四邊形不等式；假設一個並不成立的單調性，你會得到一個快速的錯誤答案，那是最危險的一種。所以前提條件不是文書作業——它就是正確性證明，略過它，等於拿一個慢而正確的程式換一個快而錯誤的程式。
也別忘了開頭的提醒：這些是漸進上的勝利。一個平衡凸包或李超樹的常數因子是真實存在的，而對小的 n，一個帶有循序記憶體存取的樸素 O(n^2) 雙重迴圈可以先跑完。前綴和儘管放手用——它們很小、而且幾乎總是有幫助——但凸包技巧、分治法動態規劃或 Knuth-Yao，則只在輸入規模或效能剖析器告訴你轉移確實是瓶頸時才動用。快速動態規劃的藝術分兩步：先做出一個狀態清晰、轉移清晰的正確動態規劃，然後，唯有當它太慢時，才去辨識那個轉移一直默默提供的是哪一種結構性技巧。