矩阵连乘问题

#include<iostream>
using namespace std;
//动态规划解决矩阵连乘问题
void MatrixChain(int *p,int n,int **m,int **s)
{
    for(int i=1;i<=n;i++)                  //初始化m[i][i]
        m[i][i]=0;
    for(int r=2;r<=n;r++)                 //矩阵链的长度2，3，4...
        for(int i=1;i<=n-r+1;i++)         //确定i
        {
            int j=i+r-1;                  //确定j,从而i,j相差的值为r
            m[i][j]=m[i][i]+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]*p[k]*p[j];
                if(t<m[i][j])
                {
                    m[i][j]=t;s[i][j]=k;
                }
            }
        }
}

//输出最优计算的次序
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)<<","<<endl;
}

编辑器加载中...