algorithm - 矩阵乘法

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