1、递归实现：

using namespace std;
/*
 * 矩阵链相乘（递归实现）
 */ 
int RecurMatrixChain(int *a, int begin, int end)
{   
    if(begin == end - 1){
    //注意矩阵与输入数组的对应关系，输入的数组除首尾元素外中间的元素都需要被两个矩阵共用
        //cout<<begin<<" "<<end<<" "<<0<<endl;
        return 0;
    }
    else{
        int i, temp, m;
        m = RecurMatrixChain(a, begin, begin + 1) +
                RecurMatrixChain(a, begin + 1, end) +
                a[begin] * a[end] * a[begin + 1];
        for(i = 2; i < end - begin; ++i){
            temp = RecurMatrixChain(a, begin, begin + i) +
                    RecurMatrixChain(a, begin + i, end) +
                    a[begin] * a[end] * a[begin + i];
            if(temp < m)
                m = temp;
        }
        //cout<<begin<<" "<<end<<" "<<m<<endl;
        return m;
    }
}

2、迭代实现：

#define N 6
using namespace std;
int m[N][N];
int s[N][N];
/*
 * 矩阵链相乘（迭代实现）
 */ 
int RecurMatrixChain(int *a, int begin, int end, int m[][N]/*存储子问题解*/, int s[][N]/*存储划分位置*/)
{   
    int i, j, k, temp_m1, temp_m2, r = end - begin;
    for(i = 1; i <= r; ++i){//相乘矩阵个数
        for(j = begin; j <= end - i; ++j){
            if(i != 1){//考虑m[j][j + i]的最小值
                temp_m1 = m[j][j + 1] + m[j + 1][j + i] + a[j] * a[j + 1] * a[j + i];
                s[j][j + i] = j + 1;
                for(k = j + 2; k < j + i; ++k){//k为j+1到j+i-1之间的一个值
                    temp_m2 = m[j][k] + m[k][j + i] + a[j] * a[k] * a[j + i];
                    if(temp_m2 < temp_m1){
                        temp_m1 = temp_m2;
                        s[j][j + i] = k;
                    }
                }
                m[j][j + i] = temp_m1;
            }
        }
    }
    return m[begin][end];
}
void Output(int s[][N], int begin, int end)
{
    //cout<<begin<<" "<<s[begin][end]<<" "<<end<<endl;
    int temp = s[begin][end];
    static int count = 1;
    if(temp == 0){
        cout<<'X'<<count++;
    }
    else{
        cout<<'(';
        Output(s, begin, temp);
        Output(s, temp, end);
        cout<<')';
    }
    //cout<<endl;
}

原理参见 屈婉玲老师 算法设计与分析 ORZ