Dynamic Programming - 解決連續矩陣相乘效率問題

這次要來討論的案例是連續矩陣相乘 !!

此案例的前景知識

大家都知道矩陣(matrix)之間相乘是不滿足交換律的

也就是說

Assume there are a “matrix A” and a “matirx B”

A x B 不等於 B x A， 平常數字的所滿足的 3 x 4 = 4 x 3 = 12 ，在矩陣的世界是不能用的

舉例

假設矩陣A為 p0 X p1 的矩陣， 矩陣B為 p1 X p2的矩陣，由上圖得知 p0 = 2， p1 = 3， p2 = 2

矩陣A為 2 (row) X 3 (column) 乘以 矩陣B為 3 (row) X 2 (column) 會得到一個 2 X 2 的矩陣C

由上圖的運算過程可知，而運算中所需要的純量乘法數是 p0 x p1 x p2 = 2 x 3 x 2 = 12，總共需要進行12個乘法才能完成 A 與 B 的合併。