代码求解

递归法

int MatrixChain1(const int* p, int i, int j,
    std::vector<std::vector<int> >&m, std::vector<std::vector<int> >& s)
{
    if (i == j)
    {
        m[i][j] =  0;
    }
    else if (m[i][j] > 0)
    {
        return m[i][j];
    }
    else
    {
        //k = i;
        int k = i;
        m[i][j] = 0 + MatrixChain1(p, k + 1, j,m,s) + p[i - 1] * p[k] * p[j];
        s[i][j] = k;
        for (k = i + 1; k < j; ++k)
        {
            int t2 = MatrixChain1(p, i, k,m,s) + MatrixChain1(p, k + 1, j,m,s) + p[i - 1] * p[k] * p[j];
            if (t2 < m[i][j])
            {
                m[i][j] = t2;
                s[i][j] = k;
​
            }
        }
    }
    return m[i][j];
} 
​

动态规划迭代解法

int MatrixChain2(const int* p, int n,
    std::vector<std::vector<int> >& m, std::vector<std::vector<int> >& s)
{
    if (n <= 1) return 0;
    for (int i = 1; i <= n; ++i)
    {
        m[i][i] = 0;
    }
    Print2Vec(m);
    for (int r = 2;r <= n;++r)
    {
        for (int i = 1;i <= n-r+1; ++i)
        {
            int j = i + r - 1;
            int k = i;
            m[i][j] = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
            s[i][j] = k;
            for (k = i + 1; k < j; ++k)
            {
                int t1 = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t1 < m[i][j])
                {
                    m[i][j] = t1;
                    s[i][j] = k;
                }
            }
​
        }
        Print2Vec(m);
    }
    return m[1][n];
}

递归回溯矩阵链乘法的最优分割方案

void Traceback(int i, int j, const std::vector<std::vector<int> >& s)
{
    if (i == j) return;
    Traceback(i, s[i][j], s); // i,k;
    Traceback(s[i][j] + 1, j, s); //k+1,j;
    cout << "Multiply A" << i << " , " << s[i][j]; 
    cout << " and A " << s[i][j] + 1 << " , " << j << endl;
}