算法|动态规划|问题5

四个矩阵M1、M2、M3和M4的维数分别为pxq、qxr、rxs和sxt，它们可以通过多种方式相乘，总的标量乘法次数不同。例如，当乘以（（M1 X M2）X（M3 X M4））时，乘法总数为pqr+rst+prt。当乘以（（M1 X M2）X M3）X M4时，标量乘法的总数为pqr+prs+pst。

如果p=10，q=100，r=20，s=5，t=80，那么所需的标量乘法数为 （A） 248000 （B） 44000 （C） 19000 （D） 25000 答复: （C） 说明： 基本上 矩阵链乘法 问题我们使用（（M1 X（M2 X M3））X M4）得到最小乘法数。

乘法总数=100x20x5（对于M2 x M3）+10x100x5+10x5x80=19000。 这个问题的小测验