Contents

理解 Dynamic Programming 3 - 用 連續矩陣相乘 例子來了解(未完成)

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 ,在矩陣的世界是不能用的

舉例

tree

假設矩陣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 的合併。