对w个矩阵加括号,使其连乘的总乘法次数最少

#include
#include
using namespace std;
const int N = 50;
class matrix
{
public:
    matrix();
    ~matrix();
    bool run();
private:
    int w;         //记录矩阵的个数    
    int **m;        //存放最优值,即最小运算量
    int **s;        //断开位置
    int *p;        //存放
    bool input();

    bool matrixChain();
    void optimalOrder(int i,int j);
};
matrix::matrix()
{
    w=0;    
    m = new int*[N];
    s = new int*[N];
    for(int i=0;i    {
        m[i] = new int[N];
        s[i] = new int[N];
    }
    p = new int[N];
}
matrix::~matrix()
{
    for(int i=0;i    {
        delete []m[i];  //二维的要先深删除
        delete []s[i];  //二维的要先深删除,再浅删除
    }
    delete []m; //浅删除
    delete []s; //浅删除
    delete []p; //一维的只删除一遍即可
}
bool matrix::input()
{
    cout<<"矩阵个数: ";
    cin>>this->w;
    cout<<"矩阵维数:";
    cin>>p[0]>>p[1];
    for(int i=2;i<=this->w;i++)
    {
        int m = p[i-1];
        cout<<"输入矩阵A"<        cin>>p[i-1]>>p[i];
        if(p[i-1]!=m)
        {
            cout<            exit(1);
        }
    }
    if(p!=NULL)
        return true;
    else
        return false;
}
//由递推公式知m[i][j]依赖于m[i,k]和m[k,j], k>=i所以m[k,j]是表中m[i,j]的同一列下面元素,  k<=j 所以m[i][k]是同一行的前面的元素,这种依赖导致了要按照对角线来推进,由下至上或由上至下都可以
bool matrix::matrixChain()
{
    if(NULL == p)
        return false;
    for(int i=1;i<=w;i++)
        m[i][i]=0;       //对解线上值是初始条件，很容易得到

        //沿对角线,小心安排迭代顺序,使得当前问题所依赖的子问题的解(前一对角线)已在表中
    for(int d=2;d<=w;d++)
        for(int i=1;i<=w-d+1;i++)
        {
            int j=i+d-1;
            m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
            s[i][j]=1;
            for(int k=i+1;k            {
                //由于除第一个为行外,后面都只存当前矩阵的列,因为前一个矩阵的列数就是当前矩阵的行数 ,满足矩阵相乘原则
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t                {
                    m[i][j] = t;
                    s[i][j] = k;        //当前断开位置，是我们括号的位置啊
                }
            }
        }
    return true;
}
//利用表格回溯找出从矩阵Ai到矩阵Aj连乘的最优组合, 参数表示 先算Ai到Aj的积 , 所以 Ai左边要有个括号, Aj右边要有个括号, 作为一个封闭的单元
void matrix::optimalOrder(int i,int j)
{
        //递归结束的基本条件
    if(i == j)                 
    {
        cout<<"A"<    }else if(i+1 == j)
    {
        cout<<"(A"<    }else{
        int k = s[i][j] ;      //为了算法的清晰起见
        cout<<"(";             //Ai左边要有个括号
        optimalOrder(i,k);
        optimalOrder(k+1,j);   
        cout<<")";          //Aj右边要有个括号
    }    
}
bool matrix::run()
{
    if(matrix::input())
    {
        if(matrix::matrixChain())
        {
            matrix::optimalOrder(1,w);
            cout<            return true;
        }
        else
            return false;
    }
    else
        return false;
    
}
main()
{
    matrix m;
    m.run();
}