矩陣乘法

Question

我正在閱讀Cormen動態規劃算法介紹。

矩陣的排序對於執行矩陣乘法很重要。如果我乘以多個矩陣並得出最佳結果，那麼如何通過爲該序列添加矩陣來保持最佳結果？

Answer 1

如果您有：

DP[i, j] = minimum cost of multiplying matrices i to through j 

然後DP[1, n]會是你的答案。

要找到DP[1, n + 1]，只適用於你用於構建表中的同一復發：

DP[1, n + 1] = min {DP[1, k] + DP[k + 1, n + 1] + multiplication cost} 
      1<=k<n+1 

這將是O(n)。