【思路】：这里我采用两种方法来实现：
（1）用三重for循环来实现：根据主对角线的方向及其右边与之平行的对角线方向，由上至下，从左到右分别求出C[i][j]的值，后面要求的值都可以根据前面所求的的值来求。
C[i][j]代表矩阵链Ai..Aj相乘的最小消耗。其中：c[i][i]=0，i=1,2,....n
求解的顺序如下：C[1][2],C[2][3],C[2][3],...,C[N-1][N],C[1][3],C[2][4]....C[N-2][N]..........C[N][N]
最后得到的C[N][N]的值就是我们所求的。
（2）备忘录方法（即递归算法）：将整个矩阵链分成两部分，然后在分别对两边的子矩阵链递归调用算法。
【程序代码】：两种方法都在其中：

#include<iostream.h>
#include<stdlib.h>
#include<limits.h>
#include<time.h>
#define MAX_VALUE 100
#define N 201 //连乘矩阵的个数(n-1)
#define random() rand()%MAX_VALUE   //控制矩阵的行和列的大小
int c[N][N], s[N][N], p[N];
int matrixchain(int n)    //3个for循环实现
{    for(int k=1;k<=n;k++)
        c[k][k]=0;
    for(int d=1;d<n;d++)
        for(int i=1;i<=n-d;i++)
        {    int j=i+d;
            c[i][j]=INT_MAX;
            for(int m=i;m<j;m++)
            {    int t=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j];
                if(t<c[i][j])
                {
                    c[i][j]=t;
                    s[i][j]=m;
                }
            }
        }
    return c[1][n];
}
void Print(int s[][N],int i,int j) //  输出矩阵连乘积的计算次序
{    if(i==j)
        cout<<"A"<<i;
    else
    {
        cout<<"(";
        Print(s,i,s[i][j]);  // 左半部子矩阵连乘
        Print(s,s[i][j]+1,j);  //左半部子矩阵连乘
        cout<<")";
    }
}
int lookupchain(int i,int j)  //备忘录方法
{
    if(c[i][j]>0)
        return c[i][j];
    if(i==j)
        return 0;
    int u=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j];
    s[i][j]=i;
    for(int k=i+1;k<j;k++)
    {
        int t=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j];
        if(t<u)
        {
            u=t;
            s[i][j]=k;
        }
    }
    c[i][j]=u;
    return u;
}
void main()
{
    srand((int)time(NULL));
    for(int i=0;i<N;i++)  //  随机生成数组p[]，各个元素的值的范围：1~MAX_VALUE
        p[i]=random()+1;
    clock_t start,end;  
    double elapsed;
    start=clock();
    //cout<<"Count: "<<matrixchain(N-1)<<endl;   //3重for循环实现
    cout<<"Count: "<<lookupchain(1,N-1)<<endl;   //备忘录方法
    end=clock();
    elapsed=((double)(end-start));///CLOCKS_PER_SEC;
    cout<<"Time: "<<elapsed<<endl;
    Print(s,1,N-1);  //输出矩阵连乘积的计算次序
    cout<<endl;
}

【总结】：两种算法的时间复杂度均为o(n3)，,随着数据量的增多，备忘录方法消耗的时间越长；我觉得是由于递归算法，随着数据量增大，调用函数的次数也增大，语句被执行的时间也越多，因此调用函数消耗的时间也增多。