Matrix-chain Multiplication Problem(矩陣鏈相乘) Back

Overview

• 求出乘次數最少的順序
• 主程序時間複雜度:
• 添加括號時間複雜度:
• 子問題個數(m數組的填寫):
• : 第i個矩陣到第j個矩陣次數的最少值 (用於記錄最優解的值)
• : 第i個矩陣到第j個矩陣相乘時, 應該先乘前個 (用於記錄最優解)
• : 第i個矩陣的兩個維數

Optimal Substructure

• 當我們知道和都是所乘次數最少的, 那麼的值一定是這兩個值相加後, 再加上.

Recursive Expression

Solution

• 最優解: 通過反向遍曆, 找到最優解.
• 最優解的值: