矩阵乘法

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)。