3892: 4.6 快速计算——矩阵连乘

给定 n 个矩阵{A1，A2，A3，…，An}，其中，Ai 和 Ai+1（i=1，2，…，n−1）是可乘的。


矩阵乘法如图 4-40 所示。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘 法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。 


例如： A1是 M5×10的矩阵； A2是 M10×100的矩阵； A3是 M100×2的矩阵。 那么有两种加括号的方法： （1）（A1 A2）A3； （2）A1（A2 A3）。 第 1 种加括号方法运算量：5×10×100+5×100×2=6000。 第 2 种加括号方法运算量：10×100×2+5×10×2=2100。 可以看出，不同的加括号办法，矩阵乘法的运算次数可能有巨大的差别！ 



矩阵连乘问题就是对于给定 n 个连乘的矩阵，找出一种加括号的方法，使得矩阵连乘的 计算量（乘法次数）小。