假设将维度为 p×q 的矩阵 G1 与维度为 q×r 的另一个矩阵 G2 相乘需要 pqr 次标量乘法。计算 n 个矩阵 G1G2G3 的乘积...... Gn 可以通过不同方式的括号来完成。如果 GiGi+1 直接相乘，则将 GiGi+1 定义为给定括号化的显式计算对。例如，在使用括号 (G1(G2G3))(G4(G5G6)) 的矩阵乘法链 G1G2G3G4G5G6 中，G2G3 和 G5G6 只是显式计算对。
考虑矩阵乘法链 F1F2F3F4F5，其中矩阵 F1、F2、F3、F4 和 F5 的维度分别为 2×25、25×3、3×16、16×1 和 1×1000。在最小化标量乘法总数的 F1F2F3F4F5 的括号中，显式计算的对是/是
仅限 F1F2 和 F3F4
仅限 F2F3
仅限 F3F4
仅限 F2F3 和 F4F5
============================================= ========================
我的方法 - 我想在一分钟内解决这个问题，但我知道的唯一方法是通过制作表格来使用自下而上的动态方法，我可以得出的另一件事是我们应该在最后是因为它的维度是 1000。所以，请问如何为这类问题培养快速的直觉!
============================================= =======================
正确答案是 F3F4
最佳答案
最重要的是要注意尺寸1×1000。如果你想最小化乘法，你最好注意它。好的，现在我们确实知道我们正在寻找的基本上是将一个小数字乘以 1000。
如果我们使用 F4F5 仔细检查，我们将乘以 16x1x1000。但是计算 F3F4 首先 ，结果矩阵的维度为 3x1。所以使用 F3F4 我们能够得到像 3,1 这样的小数字。所以，我绝不会选择 F4F5。
根据类似的逻辑，我不会选择 F2F3 并放松较小的 3 并获得更大的 25 和 16> 稍后与 1000 一起使用。
OK，对于F1F2，你可以很快发现(F1F2)(F3F4)并不是更好比 (F1(F2(F3F4))) 。所以答案是F3F4
关于algorithm - 矩阵链乘法动态规划，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50625261/