【动态规划】矩阵连乘问题

问题描述：

　　　　给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。

　　如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

　　m[ i ][ j ]  ：i = j时指矩阵A_i ，i < j时指矩阵Ai到矩阵Aj的若干矩阵连乘的最小次数。pi 指维数。

例：       

c图表示连乘矩阵中k的位置。

1.求A1-A6矩阵的最小连乘次数，就是求m[ 1 ][ 6 ]的值。

先对m[ 1 ][ 6 ]进行一次划分，

划分结果为m[ 1 ][ 1 ]+m[ 2 ][ 6 ]+p0p1p6 （ A1(A2*A3*A4*A5*A6) ），

　　　　   m[ 1 ][ 2 ]+m[ 3 ][ 6 ]+p0p2p6 ....

　　    ....  m[ 1 ][ 5 ]+m[ 6 ][ 6 ]

2.这5中情况，值最小的即为这次划分（结合律）的最优连乘顺序。

而类似m[ 2 ][ 6 ]（超过2个矩阵相乘的连乘最小次数）则也是通过划分为两部分矩阵得到的最优连乘顺序。

3.综上：m[ 1 ][ 6 ]=m[ 1 ][ 3 ]+m[ 3 ][ 6 ]+p0p3p6

　　　m[ 1 ][ 3 ]=m[ 1 ][ 1 ]+m[ 2 ][ 3 ]+p0p1p3

　　　m[ 3 ][ 6 ]=m[ 3 ][ 3 ]+m[ 4 ][ 6 ]+p2p3p6

　　　m[ 4 ][ 6 ]=m[ 4 ][ 5 ]+m[ 6 ][ 6 ]+p3p5p6

最少两个矩阵相乘，得出它们的连乘次数。然后推广到3个矩阵相乘，...... n个矩阵相乘。