矩陣連乘（matrix-chain multiplication）

你有好幾個矩陣要依固定的由左至右順序相乘，例如 A 乘 B 乘 C 乘 D。矩陣乘法滿足結合律，所以無論你怎麼加括號，答案都一樣——(A B)(C D) 與 A((B C)D) 都給出完全相同的矩陣。但所需的算術量並不相同：一個 10x100 乘以一個 100x5 要花 10 乘 100 乘 5 = 5000 次純量乘法，而糟糕的加括號方式可能比好方式多做好幾個數量級的運算。任務是找出最省的加括號方式，而不是真的去把矩陣乘出來。

用維度來編碼矩陣：第 i 個矩陣是 p[i-1] 乘 p[i]，所以矩陣 1..n 構成的鏈需要一個維度陣列 p[0..n]。令 dp[i][j] 為計算矩陣 i 到 j 之乘積所需的最少純量乘法次數。單一矩陣不需任何乘法，故 dp[i][i] = 0。對較長的鏈，你決定最後一次乘法：在 k 處分割，先算左乘積（矩陣 i..k，得到一個 p[i-1] 乘 p[k] 的矩陣）與右乘積（矩陣 k+1..j，一個 p[k] 乘 p[j] 的矩陣），再把這兩個相乘，成本為 p[i-1] 乘 p[k] 乘 p[j]。於是 dp[i][j] = 在 k 從 i 到 j-1 之間取 dp[i][k] + dp[k+1][j] + p[i-1] p[k] p[j] 的最小值。這是區間動態規劃的標準範例：按鏈長遞增填表，使兩個子乘積皆已知。

共有 O(n^2) 個區間、每個 O(n) 種分割，因此 O(n^3) 時間、O(n^2) 空間——而表格只找出最佳成本，所以要另存分割點才能還原出實際的加括號方式。這是說明「最佳子結構加上重疊子問題要用動態規劃而非貪婪」的教科書範例：沒有任何簡單的貪婪規則（例如總是先乘最小維度）在一般情況下正確。這裡的成本是教科書乘法演算法下的純量乘法次數；改用 Strassen 式的快速乘法會改變成本模型，但這個（乘法）順序問題與其動態規劃就是標準教科書版本。