矩阵连乘的DP，两种方法(自下至上、自顶至下)

andalousie

基本上百度一下都可以搜到矩阵连乘的算法。大家写的都差不多是同一个思路(bottom-up DP，自下而上的动态规划)。这里再提供一个速度相仿的自上而下(top-down)的解法。代码属于C++。

// See the Cormen book for details of the following algorithm
#include<iostream>
#include<cstdio>
#include<climits>

class MatrixChain
{
        int     n;
        int ** m;
        int ** s;
public:
        MatrixChain(int size)
                :n(size)
        {
                /* For simplicity of the program, one extra row and one extra column are
       allocated in m[][].  0th row and 0th column of m[][] are not used */
                m = new int* [n+1];
                s = new int* [n+1];
                for (int t = 0; t <= n; ++t)
                {
                        m[t] = new int[n+1];
                        s[t] = new int[n+1];
                }
        }
        ~MatrixChain()
        {
                for (int t = 0; t <= n; ++t)
                {
                        delete [] m[t];
                        delete [] s[t];
                }
                delete [] s;
                delete [] m;
        }
        int MatrixChainOrder(int p[]);
        int MatrixChainOrderTD(int p[]);
        void traceback(int i, int j);
        int topdown(int p[], int i, int j);
};

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChain::MatrixChainOrder(int p[])
{
    int i, j, k, L, q;

    /* m[i,j] = Minimum number of scalar multiplications needed to compute
       the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
       p[i-1] x p[i] */

    // cost is zero when multiplying one matrix.
    for (i = 1; i <= n; i++)
        m[i][i] = 0;
 
    // L is chain length.  
    for (L=2; L<=n; L++)   
    {
        for (i=1; i<=n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            for (k=i; k<=j-1; k++)
            {
                // q = cost/scalar multiplications
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                                {
                    m[i][j] = q;
                                        s[i][j] = k;
                                }
            }
        }
    }
    return m[1][n];
}

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChain::MatrixChainOrderTD(int p[])
{
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;
        for (int u = 0; u <= n; ++u)
                for (int v = 0; v <= n; ++v)
                        s[u][v] = 0;
 
    int result = topdown(p, 1, n);
    return result;
}

void MatrixChain::traceback(int i, int j)
{
        if(i == j) return;
        traceback(i, s[i][j]);
        traceback(s[i][j]+1, j);
        std::cout << "A[" << i << ',' <<s[i][j]
                << "] * A[" << s[i][j]+1 << ',' << j
                << "]\n";
}

int MatrixChain::topdown(int p[], int i, int j)
{
        if(i != j)
        {
                if(s[i][j]) return m[i][j];
                m[i][j] = INT_MAX;
                int q;
                for(int k = i; k < j; ++k)
                {
                        q = topdown(p, i, k) + topdown(p, k + 1, j) + p[i-1]*p[k]*p[j];
                        if (q < m[i][j])
                        {
                                m[i][j] = q;
                                s[i][j] = k;
                        }
                }
        }
        return m[i][j];
}

int main()
{
        int arr[] = {3023, 3533, 155, 203, 2573, 3093};
        int size = sizeof(arr)/sizeof(arr[0]) - 1;
        MatrixChain mc(size);
        printf("Minimum number of multiplications is %d \n",
                       mc.MatrixChainOrder(arr));
        printf("Minimum number of multiplications is %d \n",
                       mc.MatrixChainOrderTD(arr));
        mc.traceback(1, size);
        return 0;
}