1. 问题
设A1，A2，….，An为n个矩阵的序列，其中Ai为Pi-1 * Pi阶矩阵，这个矩阵链的输入用向量P=<P0,P1,…,Pn>给出.
给定向量P，确定一种乘法次序，使得基本运算的总次数达到最小。
2. 解析
这道题可以用枚举法:
枚举所有可能的乘法次序，针对每种次序计算基本运算的次数，从中找出具有最小运算次数的乘法次序，每一种乘法次序对应了一种在n个项中加n-1对括号。
也可以用动态规范：
Ai~j：表示矩阵链相乘的子问题：Ai，A+1，…Aj;
m[i,j]：表示得到乘积Ai-j所用的最少基本运算次数。
转移方程为
命题m[i..j]=min{m[i,k]+m[k+1,j]+Pi=1PkPj}满足优化原则，即m[i..j]最小值时，m[i,k]和m[k+1,j]也是最小的
3. 设计
递归函数：
void PrintAnswer(int(*s)[N],int i,int j)
{
if(i==j)
{
cout<<"A"<<i;
}
else
{
cout<<"(";
PrintAnswer(s,i,s[i][j]);
PrintAnswer(s,s[i][j]+1,j);
cout<<")";
}
}
Dp函数：
void MatrixChainOrder(int *p,int (*m)[N],int (*s)[N],int length)
{
int n=length-1;
int l,i,j,k,q=0;
//m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0;
for(i=1;i<length;i++)
{
m[i][i]=0;
}
//l表示矩阵链的长度
// l=2时，计算 m[i,i+1],i=1,2,...,n-1 (长度l=2的链的最小代价)
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1; //以i为起始位置，j为长度为l的链的末位，
m[i][j]=0x7fffffff;
//k从i到j-1,以k为位置划分
for(k=i;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
cout << m[1][N-1] << endl;
}
4. 分析
样例推导：
递归算法分析：
迭代算法 O(n^3);
5. 源码
kitalekita/矩阵链乘法.cpp at main · kitalekita/kitalekita (github.com)