區間動態規劃（interval DP）

想像一排物件——串在線上的珠子、單字裡的字母、籬笆上的木板——而你要完成的工作只能靠反覆合併或切分相鄰的片段。不論怎麼做，你處理的永遠是這一排中一段連續的區間，絕不會是零散的幾個。區間動態規劃正是為這類問題而生的模式：你記住部分答案的對象，是從位置 i 到位置 j 的一段區間，寫成 dp[i][j]，而你先算短區間、後算長區間，逐步堆出答案。

狀態 dp[i][j] 通常表示解決涵蓋位置 i 到 j 這一小排的最佳成本（或方案數）。轉移會挑一個分割點：dp[i][j] 由較小的左片 dp[i][k] 與較小的右片 dp[k+1][j]，再加上接合的成本所組成，並在 i 與 j 之間每個合法分割 k 上取最小（或求和）。讓這做法正確的關鍵是最佳子結構：一旦決定了最後一次合併發生在哪裡，左右兩側就是各自獨立、可以單獨求解的小排。由於每個小排都比 [i, j] 短，你按長度遞增來填表——先所有長度 1 的區間，再長度 2，依此類推——於是每個 dp[i][k] 與 dp[k+1][j] 在你需要它之前都已備妥。典型迴圈是：len 從 2 到 n，對每個 i 令 j = i + len - 1，再在 k 從 i 到 j-1 之間取 dp[i][k] + dp[k+1][j] + cost(i, k, j) 的最佳值。

有 n 個位置時約有 n^2 / 2 個區間，每個最多嘗試 n 個分割點，因此樸素版本耗時 O(n^3)、空間 O(n^2)。對幾百個位置而言這完全夠用，也正是矩陣連乘與最佳二元搜尋樹這些經典問題的家。當成本函數性質良好時，Knuth-Yao 四邊形不等式能削減內層分割搜尋，把整體降到 O(n^2)。常見錯誤是讓左右兩側重疊、或把分割元素重複算了兩次；要小心合併點究竟屬於左片、右片、還是都不屬於。