问题：给定n个矩阵A1,A2,...,An，使得n个矩阵的连乘A1A2...An的计算量最小。

因为矩阵的乘法满足结合律，所以问题简化为怎么加括号。

使用动态规划解决该问题：

1.分析{zy}解的结构（找出{zy}解的性质，并刻画其结构特征）

记A1A2...An为A[i,j]，计算次序在Ak和Ak+1之间断开，所以，得计算A[1,k]和A[k+1,n]，然后再相乘得到A[1,n]，依此计算顺序总计算量为A[1,k]的计算量加上A[k+1,n]的计算量，再加上A[1,k]和A[k+1,n]相乘的计算量。

2.建立递归关系(递归定义{zy}值）

设计算A[i,j]，1<=i<=j<=n，所需的最少数乘次数为m[i][j]，则原问题的{zy}值为m[1][n]。

当i=j，m[i][j]=0；

当i<j，m[i][j]=min(i<=k<j){m[i][k]+m[k+1][j]+p(i-1)p(k)p(j)}

{zy}次序中断开位置k记为s[i][j]。

3.计算{zy}值（以自底向上的方式计算出{zy}值）

void MatrixChain(int *p,int n,int **m,int **s)

{

  for(int i=1;i<=n;i++) m[i][i]=0

  for(int r=2;r<=n;r++)

     for（int i=1;i<=n-r+1;i++){

      int j=i+r-1;

      m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];

      s[i][j]=i;

      for(int k=i+1;k<j;k++){

        int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

        if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}

      }

      }

} 

算法首先计算出m[i][i]=0；然后按矩阵的递增的方式依此计算m[i][i+1],i=1,2,3,...,n-1;m[i][i+2]...其中r就是这个链长，两个for循环就是填表的过程，这里的二维数组m就是表格，用来记录已经解决的子问题的答案，不管是不是以后要用到，都记录下来。 

4.构造{zy}解（根据计算{zy}值时得到的信息，构造{zy}解）

表格s中记录了{zy}解的断开点信息。

void Traceback(int i,int j,int **s)

{

 if(i==j) return;

 Traceback(i,s[i][j],s);

 Traceback(s[i][j]+1,j,s);

 cout<<"Multiply A "<<i<<","<<s[i][j];

 cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;

}