辨識可批次化的轉移（recognizing batchable transitions）

一個慢的動態規劃通常慢得有個具體原因：每個狀態的轉移做了大量重複工作，而這些工作與相鄰狀態的轉移彼此重疊。辨識可批次化轉移的本領，就是那雙能看出此重疊的診斷之眼，並問：「我能不能把這許多相似的轉移一起、成批地算出來，而非一次一次地痛苦掃描？」它與其說是單一演算法，不如說是那個告訴你問題正渴求「哪個」加速工具——前綴和、單調結構、凸包優化、分治、Knuth 優化——的後設本領。

辨識的方法是觀察內層迴圈的形狀，也就是讓 dp[i] 花費超過 O(1) 的那部分。幾種特徵反覆出現。若 dp[i] 對一個連續的前一狀態窗口求和或取簡單聚合，且相鄰 i 的窗口大多重疊，則前綴和（或滑動窗口聚合）把它們各批次成 O(1)。若 dp[i] 是在較早狀態上取 min/max，而每個貢獻一個關於某索引的線性函數 m_j * x + b_j，那就是凸包優化（或 Li Chao）的特徵。若轉移是 dp[i][j] = 在 k 上取 dp[i-1][k] + cost(k, j) 的最小值，且最佳 k 對 j 單調，則分治動態規劃優化適用；若成本服從四邊形不等式，Knuth 優化會縮窄區間搜尋。共同的線索：樸素轉移為每個新狀態重算一個其實與前一狀態幾乎沒變的聚合——所以你改為增量地維護那個聚合。

這為何重要：O(n^2) 與 O(n log n) 動態規劃之間的差別，往往不是一個新的遞迴，而是同一個遞迴配上一個批次化的轉移，而辨識這個模式正是把「正確但太慢」的解變成「快」的關鍵。誠實的提醒：每個工具都附帶前置條件（前綴和要可反轉、凸包要斜率單調或退而用 Li Chao、其餘要最佳分割單調或四邊形不等式），所以辨識特徵是第一步、驗證前置條件是第二步。誤讀特徵——在貢獻其實非線性時套用凸包優化、或在分割不單調時套用分治優化——會產生快速而自信的錯誤答案。這個辨識是一個待檢查的假設，而非一張通行證。