TreeviewCopyright © aleen42 all right reserved, powered by aleen42
Matrix-chain Multiplication Problem(矩陣鏈相乘) Back
Overview
- 求出乘次數最少的順序
- 主程序時間複雜度:
- 添加括號時間複雜度:
- 子問題個數(m數組的填寫):
: 第i個矩陣到第j個矩陣次數的最少值 (用於記錄最優解的值)
: 第i個矩陣到第j個矩陣相乘時, 應該先乘前個 (用於記錄最優解)
: 第i個矩陣的兩個維數
Optimal Substructure
- 當我們知道
和
都是所乘次數最少的, 那麼的值一定是這兩個值相加後, 再加上
.
Recursive Expression
Solution
- 最優解: 通過反向遍曆, 找到最優解.
- 最優解的值:
As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.
Notice: This plugin has used Cookie to store your token with an expiration.