本文的閱讀等級：初級
給定一序列的可乘矩陣，這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律，所以不論採用何種相乘順序，最後的結果總是一樣的。例如，$$A$$ 是 $$3\times 5$$，$$B$$ 是 $$5\times 2$$，$$C$$ 是 $$2\times 4$$，$$D$$ 是 $$4\times 6$$ 階矩陣，總計有 $$5$$ 種方式刮號乘積，如下：
$$((AB)C)D$$，$$(A(BC))D$$，$$(AB)(CD)$$，$$A((BC)D)$$，$$A(B(CD))$$
雖然矩陣鏈乘積相同，但不同的乘法順序所耗費的運算量並不相同。例如，若以乘法運算為計數單位，$$A(BC)$$ 需要 $$(5\times 2\times 4)+(3\times 5\times 4)=40+60=100$$ 個運算，而 $$(AB)C$$ 只使用 $$(3\times 5\times 2)+(3\times 2\times 4)=30+24=54$$ 個運算，第二種計算方式明顯優於第一種方式。考慮一般情況，如果有 $$n$$ 個矩陣相乘，如何決定最佳的矩陣乘法執行順序？這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量，不過，這僅適用於小 $$n$$ 的情況。當 $$n=10$$，刮號乘積有 $$16,796$$ 種可能，而當 $$n=20$$ 時，總共有 $$6,564,120,420\approx 6\times 10^9$$ 種可能！對於長矩陣鏈，不難理解蠻力檢查是絕對不可行的。
