矩阵链乘动态规划

Question

假设维数p×q的矩阵G1与维数q×r的另一个矩阵G2相乘需要pqr标量乘法。N矩阵G1G2G3…乘积的计算。。Gn可以用不同的方式通过括号来完成。如果GiGi+1被直接乘以，则将它们定义为给定偏执的显式计算对。例如，在使用括号的矩阵乘法链G1G2G3G4G5G6 (G1( G2G3 ))(G4( G5G6 ))中，G2G3和G5G6仅是显式计算对。

考虑矩阵乘法链F1F2F3F4F5，其中矩阵F1、F2、F3、F4和F5的维数分别为2×25、25×3、3×16、16×1和1×1000。在使标量乘法总数最小化的F1F2F3F4F5括号中，显式计算的对是/are。

仅限F1F2和F3F4

仅限F2F3

仅限F3F4

仅限F2F3和F4F5

=======================================================================

我的方法--我想在一分钟内解决这个问题，但我所知道的唯一方法是使用自下而上的动态方法，做一个表，而我可以得出的另一个结论是，我们最后应该用F5乘积，因为它的dimension.So中有1000个，请为这类问题建立快速的直觉！

======================================================================

正确答案是F3F4

Answer 1

最重要的是尺寸1×1000。如果你想要最小化乘法，你最好小心点。好的，现在我们知道我们要找的基本上是用1000乘以一个小数字。

仔细检查一下，如果我们使用F4F5，我们将把16x1x1000乘以。而计算F3F4 first，其结果矩阵具有维数3x1。因此，对于F3F4，我们可以得到像3,1这样的小数字。所以，我不可能和F4F5一起去。

按照类似的逻辑，我不会使用F2F3，也不会松开较小的3，得到更大的25和16，以便稍后与1000一起使用。

(F1F2)(F3F4) OK，对于F1F2，您可以很快发现并不比(F1(F2(F3F4)))更好。所以答案是F3F4