1、遞歸實(shí)現(xiàn)：

using namespace std;
/*
 * 矩陣鏈相乘（遞歸實(shí)現(xiàn)）
 */ 
int RecurMatrixChain(int *a, int begin, int end)
{   
    if(begin == end - 1){
    //注意矩陣與輸入數(shù)組的對(duì)應(yīng)關(guān)系，輸入的數(shù)組除首尾元素外中間的元素都需要被兩個(gè)矩陣共用
        //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、迭代實(shí)現(xiàn)：

#define N 6
using namespace std;
int m[N][N];
int s[N][N];
/*
 * 矩陣鏈相乘（迭代實(shí)現(xiàn)）
 */ 
int RecurMatrixChain(int *a, int begin, int end, int m[][N]/*存儲(chǔ)子問題解*/, int s[][N]/*存儲(chǔ)劃分位置*/)
{   
    int i, j, k, temp_m1, temp_m2, r = end - begin;
    for(i = 1; i <= r; ++i){//相乘矩陣個(gè)數(shù)
        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(luò)+i-1之間的一個(gè)值
                    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;
}

原理參見 屈婉玲老師 算法設(shè)計(jì)與分析 ORZ