动态规划：矩阵连乘问题

问题描述

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
假设矩阵连乘AiAi+1…Aj记为A[i:j],i<=j;

分析最优解的结构

特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1：j]的次序也是最优的。如下图：

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系

假设A[i:j]的最少数乘次数是m[i][j]，那么原问题的最优解就是m[i][n]；
假设：
A1=50x10,
A2=10x40,
A3=40x30,
A4=30x5,
那么p0=50,p1=10,p2=40,p3=30,p4=5;
若当前的计算次序为（A1A2）（A3A4），数乘次数：
a.M=A1A2的数乘次数=50x10x40，M的矩阵维度是50x40；
b.N=A3A4的数乘次数=40x30x5；N的矩阵维度是40x5;
c.MN的数乘次数=50x40x5；
总的数乘次数m[1][4]=a+b+c=m[1][2]+m[3][4]+p0p2p4;

当 i=j时，A[i:j]=0;
当i<j时，m[i][j]=m[i][k]+m[k+1][j]+p[i-1]p[k]p[j];
1
2

因此，递归公式的定义如下：

算法计算顺序的分析

假设当前有6个矩阵连乘，矩阵的初始状态如下：

根据上表可知：
p0=30,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25;
根据递推公式可以得出如下图的计算过程：
在上图中1号线表示的是总体的计算顺序是从2开始计算，到6号结束；

上表记录的是最少数乘次数m[i][j]的值，对角线是i=j的情况，此时的m[i][j]=0；
根据递归公式：m[i][j]=m[i][k]+m[k+1][j]+p[i-1]p[k]p[j],i<=k<j,计算m[1][2]的时候k=i=1,所以m[1][2]的计算方式如下：
m[1][2]=m[1][1]+m[2][2]+p[0]p[1]p[2]=30x35x15=15750;
同理，m[2][3]=m[2][2]+m[3][3]+p[1]p[2]p[3]=2625;
当计算m[1][3]的时候，有两种计算方式分别是（A1A2）A3和A1（A2A3），k的取值有1,2两种可能。

当k=1时，m[1][3]=m[1][1]+m[2][3]+p0p1p3=0+2625+30x35x5=7875;
当k=2时，m[1][3]=m[1][2]+m[3][3]+p0p2p3=1575
1