动态规划 - 最佳断点

Question

我了解到使用动态规划，矩阵链乘法问题可以在n^3次解决，而对于最优二叉树问题，我们也有n^3次，但是我们可以优化到n ^2。 为什么是这样？我得到一个说法，这是因为在矩阵乘法问题中，链 M(i,n) 的最优断点可能大于链 M(i+1,n) 的最优断点。有人可以帮我理解这个吗？为什么在矩阵乘法问题中是这样，而在最优二叉树问题中却不是？

谢谢

Answer 1

给定作为 I2 的子区间的键 I1 的区间，I1 上的最优二叉树的查询成本不大于 I2 上的最优二叉树的查询成本（这应该是相当直观的，但正式地，采用 I2 的最优树并通过标准算法从中重复删除键）。这意味着您可以将寻找最佳断点的过程视为两半之间的一种平衡过程。

这对于矩阵链来说是不正确的：乘以 (100, 100), (100, 100) 的成本远大于 (100, 100), (100, 100), (100, 1),因为两个矩阵-向量乘法 比矩阵-矩阵便宜很多。