具體分析見算法導論第十五章，代碼如下：
[cpp]
#include<iostream>
using namespace std;
//p為矩陣鏈，p[0],p[1]代表第一個矩陣，p[1],p[2]代表第二個矩陣，length為p的長度
//所以如果有六個矩陣，length=7，m為存儲最優結果的二維矩陣，t為存儲選擇最優結果路線的
//二維矩陣
void MatrixChainOrder(int *p,int (*m)[10],int (*t)[10],int length)
{
int n=length-1;
int i,j,k,q,num=0;
//A[i][i]只有一個矩陣，所以相乘次數為0，即m[i][i]=0;
for(i=1;i<length;i++)
{
m[i][i]=0;
}
//i代表矩陣鏈的長度，i=2表示有兩個矩陣相乘時如何劃分
for(i=2;i<=n;i++)
{
//j表示從第j個矩陣開始的i個矩陣如何劃分是最優
for(j=1;j<=n-i+1;j++)
{
//k為從第j個數i個矩陣就是k，從j到k表示他們之間的i個矩陣如何劃分
k=j+i-1;
//m[j][k]存儲了從j到k使用最佳劃分所得到的最優結果
m[j][k]=0x7fffffff;
//q為介於j到k-1之間的數，目的是利用q對j到k之間的矩陣進行試探性的劃分，
//從而找到最優劃分，這是一種遍歷性的試探。
for(q=j;q<=k-1;q++)
{
num=m[j][q]+m[q+1][k]+p[j-1]*p[q]*p[k];
if(num<m[j][k])
{
m[j][k]=num;
t[j][k]=q;
}
}
}
}
}
void PrintAnswer(int(*t)[10],int i,int j)
{
if(i==j)
{
cout<<"A"<<i;
}
else
{
cout<<"(";
PrintAnswer(t,i,t[i][j]);
PrintAnswer(t,t[i][j]+1,j);
cout<<")";
}
}
int main()
{ www.2cto.com
int p[7]={30,35,15,5,10,20,25};
int m[10][10],t[10][10];
MatrixChainOrder(p,m,t,7);
PrintAnswer(t,1,6);
return 0;
}
作者：liuzhanchen1987
