algorithm - 矩阵乘法子问题图顶点度

Question

我正在研究动态规划，在 Cormen 的算法导论的第 15.2 章中读到:

For matrix-chain multiplication, if we were to draw the subproblem graph, it would have O(n^2) vertices and each vertex would have degree at most n - 1, giving a total of O(n^3) vertices and edges.

当我绘制 n = 4 的图形时，我得到:

但是，顶点 M[1, 4] 的度数为 6 > 4 - 1。我误解了什么？

Answer 1

解决一个子问题应该会给你一个主要问题的解决方案，尽管可能不是最好的。所以，这里的一个子问题是计算两个产品，而不是一个。对于 n=4 的产品 A1 A2 A3 A4，我们有三个子问题，即 n-1:(A1, A2 A3 A4), (A1 A2, A3 A4) 和 (A1 A2 A3, A4).

编辑。书中还写着:

Thus, we can build an optimal solution to an instance of the matrix-chain multiplication problem by splitting the problem into two subproblems (optimally parenthesizing Ai ... Ak and Ak+1 ... Aj), ...

因此，子问题是计算单个产品，而不是两个产品。看来要么书上对某个子问题的定义不一致，要么n-1 bound不正确，应该是2(n-1)。