基本思想：

         1．按照2个矩阵乘积的标准算法，若一个p×q的矩阵A和一个s×t的矩阵B相乘（当然s和q要相等），要进行三重循环，总共需要pqr次数乘，显然这是一个比较的的数。

         2．通过简单分析，我们易知给连乘矩阵完全加括号方式对应一种矩阵连乘的计算次序，而这种计算次序会改变计算矩阵连乘的计算量，再试想如果是n个矩阵进行连乘那将会要太多次数乘，所以有必要做一个算法找出怎样合理的给连乘矩阵完全加括号以找出最少计算量的计算方法。

         3．穷举搜索法是最容易想到的方法，但是它本身是一个计算量非常大的算法，对于n个矩阵的连乘问题，不同的计算次序是随n的增大呈指数增长的。

         4．尝试用动态规划算法解决上面问题：首先由于A【1：n】（表示1到n个矩阵连乘）如果是最优解，那么它包含的A【1：k】和A【k＋1：n】也是最优解，即矩阵连乘求最优解符合动态规划中的最优子结构性质；再次由于A【i：j】的最少数乘次数m【i】【j】可以表示为m【i】【j】＝m【i】【k】＋m【k＋1】【j】＋pj－1pkpj（其中k是断开点），所以它也可以设计成一个具有递归关系的算法。

         5．具体实现：按照m【1】【n】的递归性以自底向上的方式进行计算，在计算中用m【】【】数组记录已经计算过的自问题的答案，m【i】【j】表示A【i：j】的最少数乘次数，并且用数组s【】【】来表示对应的m【】【】数组值的最优断开点。

         程序由两个函数组成：1）、void MatrixChain(int p[],int n)用来产生数组m和s，是关键部分；2）、int Traceback(int i,int j)是用来找出s数组中记录的最优断开点的函数。程序中我把m和s数组都给了输出，方便观察、研究。

程序如下：

#include <iostream>
#include <iomanip>
using namespace std;

#define SIZE 6                         //控制参与连乘矩阵的个数
int m[SIZE][SIZE],s[SIZE][SIZE];

void MatrixChain(int p[],int n)        //用来产生数组m和s，是关键部分
{
for(int a=0;a<n;a++) m[a][a]=0;
for(int r=2;r<=n;r++)
   for(int i=0;i<n-r+1;i++)
   {
    int j=i+r-1;
    m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];
    s[i][j]=i+1;
    for(int k=i+1;k<j;k++)
    {
     int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
     if(t<m[i][j])
     {
      m[i][j]=t;
      s[i][j]=k+1;
     }
    }
   }
}

int Traceback(int i,int j)     //找出s数组中记录的最优断开点
{
if(i==j) return -1;
Traceback(i,s[i][j]-1);
Traceback(s[i][j],j);
cout<<"包含矩阵 A"<<s[i][j];
cout<<"的部分与包含矩阵 A"<<(s[i][j]+1)<<"的部分结合，放在一个括号中"<<endl;
return 0;
}

void main()
{
int p[SIZE+1]={30,35,15,5,10,20,25};      //p记录矩阵的行列数
    MatrixChain(p,SIZE);
cout<<"输出m矩阵为："<<endl;
for(int i=0;i<SIZE;i++)
{
   for(int j=0;j<SIZE;j++)
   {
    cout<<setw(6)<<m[i][j]<<" ";
   }
   cout<<endl;
}
cout<<endl<<endl;
cout<<"输出s矩阵为："<<endl;
for(int a=0;a<SIZE;a++)
{
   for(int b=0;b<SIZE;b++)
   {
    cout<<setw(6)<<s[a][b]<<" ";
   }
   cout<<endl;
}
cout<<endl<<endl;
Traceback(0,5);
}