矩陣鏈乘積 矩阵链乘积英語Matrix chain multiplication或Matrix Chain Ordering ProblemMCOP是可用動態規劃解决的最佳化问题給定一序列矩陣期望求出相乘這些矩陣的最有效方法此問題並不是真的去執行其乘法而只是決定執行乘法的順序而已 因為矩陣乘法具有結合律所有其運算順序有很多種選擇換句話說不論如何括號其乘積最後結果都會是一樣的例如若有四個矩陣 A displaystyle A  B displaystyle B  C displaystyle C 和 D displaystyle D 將可以有 A B C D   A B   C D   A  B C D   A  B C  D     displaystyle ABCDABCDABCDABCD 但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目即其效率例如設 A displaystyle A 為一    displaystyle times  矩陣 B displaystyle B 為    displaystyle times  矩陣與 C displaystyle C 為    displaystyle times  矩陣則  A B  C displaystyle ABC 有                      displaystyle times times times times  個運算 A  B C  displaystyle ABC 有                      displaystyle times times times times  個運算 明顯地第一種方式要有效多了既然已確認過此問題了那要如何決定n個矩陣相乘的最佳順序呢可以比較每一順序的運算量使用蠻力但這將需要時間On是一種非常慢且對大n不實在的方法那解決方法如我們將看到的是將問題分成一套相關的子問題以解答子問題一次而再使用其解答數次即可以徹底地得出其所需時間此一方法稱為動態規劃