一種新形狀的子問題：區間
在這座階梯的第一階裡，子問題通常以前綴命名——「前 i 件物品」、「前 i 個字元」。那行得通，是因為答案靠一次加入一個元素、由左而右地長大。但有一整族問題拒絕被那樣切：你只能靠合併兩個相鄰的片段來推進，而你造出的那個片段本身又是一段必須再被合併的連續區間。對這些問題，自然的子問題不是前綴而是區間——從位置 i 到位置 j 的一段連續範圍——而建立其上的技巧就叫 區間動態規劃。
因此狀態是二維的：dp[i][j] 存放從 i 到 j（含兩端）這段區間的最佳答案。這樣命名狀態，正是你在 定義狀態 時學到的同一套紀律——它必須充分（未來所依賴的一切都被兩個端點所捕捉）又最小（不多攜一物）。真正全新的是計算順序。前綴型動態規劃由左而右填；區間型動態規劃則依長度遞增來填，因為一段較長區間的答案，只由嚴格落在它內部的較短區間建出，所以那些都必須先備妥。
旗艦範例：替矩陣鏈加括號
這就是讓區間動態規劃豁然開朗的問題。你必須以固定的由左而右順序，把一串矩陣相乘，比方說 A 乘 B 乘 C 乘 D。矩陣乘法滿足結合律，所以每一種加括號的方式——(A B)(C D)、A((B C)D)，諸如此類——都產生同一個結果矩陣。但算術成本卻天差地別。把一個 p×q 矩陣乘上一個 q×r 矩陣，要花 p 乘 q 乘 r 次純量乘法，所以你把這條鏈收攏的順序，能讓總工作量相差好幾個數量級。矩陣鏈乘法的任務，是找出最省的加括號方式——而不是真的去乘任何東西。
各個維度由單一陣列捕捉。若矩陣是 A1, A2, ..., An，令 p[0], p[1], ..., p[n] 為尺寸，使 Ak 是 p[k-1]×p[k]——那一列數字就編碼了整條鏈。現在來體會為什麼暴力法毫無希望：n 個矩陣相異的加括號方式有第 (n-1) 個卡塔蘭數那麼多，它的成長像 4^n 除以一個多項式。把它們全試一遍是 指數級的，所以我們想要動態規劃所給的那種有紀律的收攏。關鍵觀察是：任何一種加括號的方式，無論巢狀得多深，都恰有一個最外層的乘法——也就是最後執行的那一次。
分割點，以及它給出的遞迴
把注意力固定在從 i 到 j 這段矩陣的區間上，並把 dp[i][j] 定義為計算它們乘積所需的最少純量乘法次數。不論最佳的加括號方式是什麼，它的最後一次乘法都會在某個介於 i 與 j-1 之間的分割點 k 處，把鏈切成一個左塊（矩陣 i 到 k）與一個右塊（矩陣 k+1 到 j）。左塊產生一個 p[i-1]×p[k] 的矩陣，右塊產生一個 p[k]×p[j] 的矩陣，把這兩者相乘要花 p[i-1] 乘 p[k] 乘 p[j]。我們不知道最好的 k，所以把每一個都試過、留下最便宜的——而最關鍵的是，每一塊的成本本身就是一個最佳子答案，即 dp[i][k] 與 dp[k+1][j]，這正是 最佳子結構在發揮作用。
dp[i][j] = 0 if i == j (one matrix, nothing to multiply)
dp[i][j] = min over k in [i .. j-1] of
dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] if i < j
answer = dp[1][n]
fill order: increasing segment length L = 1, 2, ..., n-1
for L = 1 to n-1:
for i = 1 to n-L:
j = i + L
dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] )把這條 轉移念出來，它幾乎自己就敘述了自己：「把矩陣 i..j 相乘最省的方式，是在我能下最後一刀的所有位置中，取左塊成本加右塊成本加接合代價的最小值。」基底情況是 dp[i][i] = 0——單一矩陣根本不需要乘法。注意 dp[i][j] 永遠只讀取更短區間的項（只要 i < j，i..k 與 k+1..j 都嚴格落在 i..j 內部），這正是為什麼 計算順序必須依長度遞增：先處理所有長度為 1 的區間，再長度為 2，依此類推，使一格所需的每個較小區間都已是最終值。
它的成本，以及為何是 O(n^3) 而非 4^n
執行時間直接從表格落出，而且就是你一路用到的同一個乘積：（相異狀態的個數）乘以（每個狀態的工作量）。區間 [i, j] 有 O(n^2) 個，算出其中一個要掃描至多 O(n) 個分割點 k、每處做 O(1) 算術——所以總共是 O(n^3)。這是從暴力法的卡塔蘭數 4^n，驚人地塌縮到一個三次多項式：對 n = 30 個矩陣，暴力法面對天文數字般多的加括號方式，而動態規劃只做約 27000 次廉價運算。那個指數級的爆炸純粹是同一批區間的重算，而表格把它全部回收了。
現在就標出一個誠實的極限，因為它形塑了本階其餘的部分。O(n^3) 已經很好，但對某些區間動態規劃，連三次方都太慢，人們也找到了削減它的方法。當成本函數性質良好時，最佳分割點會隨著區間長大而單調移動——它從不往回跳——利用這點，能把矩陣鏈式的動態規劃從 O(n^3) 朝 O(n^2) 推進，途徑是 Knuth-Yao 四邊形不等式，或是分治型動態規劃最佳化。那些是貨真價實的加速，但它們倚賴的額外條件並非總是成立；上面那條樸素的 O(n^3) 遞迴，才是永遠管用、值得信賴的預設。
從成本到方案：重建加括號方式
上面的表回答了「最省能有多省？」卻沒回答「我究竟該怎麼加括號？」——而光一個數字鮮少令人滿意。解法是 重建解的標準手法：在 dp[i][j] 旁邊，另存一張表 split[i][j]，記下對那段區間達成最小值的那個 k。這張分割表是動態規劃所做每個決定的緊湊紀錄，由它你能還原出完整的加括號方式，而不必重算任何成本。
- 在填 dp[i][j] 時，每當某個分割點 k 給出嚴格更小的值，就記下 split[i][j] = k。填完後，split[1][n] 持有最佳方案最外層的那一刀。
- 要印出區間 i..j 的加括號方式，看 k = split[i][j]：若 i 等於 j，就只印矩陣 Ai；否則印一個左括號，對 i..k 遞迴、對 k+1..j 遞迴，再印一個右括號。
- 這趟回溯對最佳方案的每段區間各觸及一次，所以重建只是在 O(n^3) 的填表之上多做 O(n) 的工作——表一旦建好，方案幾乎是免費的。
這同一個區間形狀的模式——狀態 dp[i][j]、一個標定最後一步操作的分割點、依長度遞增填表、以及一張供重建用的分割表——就是你會在區間動態規劃中反覆重用的範本。它驅動 最佳二元搜尋樹，其中分割點是樹根、成本是期望搜尋深度；它也驅動多邊形三角剖分、最佳字串加括號，以及「戳氣球」式的合併遊戲。矩陣鏈不過是最乾淨的第一個實例，所以你在此練出的肌肉記憶可直接遷移。接下來我們會離開這條直線、把區間放到一旁，讓子問題活在一棵樹的節點上。