矩阵链乘法

矩阵A和矩阵B能够相乘，只有当矩阵A和矩阵B相容。

矩阵链乘法的前提就是降低矩阵的乘法规模。之所以可以这样，是因为矩阵相乘满足结合律。

我们可以这样去想，我们使用使用一个分割线，把矩阵链分成两份，一份左，一份右，如果左右的矩阵链的乘法次数最少，那么分割线处的乘法次数有如下等式：

公式一

公式二

代码如下：

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

struct S_Matrix {
    int X;
    int Y;

    S_Matrix(int x, int y) 
    {
        X = x;
        Y = y;
    }
};

void Output(const vector<vector<int> > & vecNum)
{
    for (int i=0; i<vecNum.size(); ++i) {
        for (int j=0; j<vecNum[i].size(); ++j) {
            cout << setw(10) << vecNum[i][j] << " ";
        }
        cout << endl;
    }
}

void OutputMatrixVec(const vector<S_Matrix> & vecMatrix) 
{
    for (int i=0; i<vecMatrix.size(); ++i) {
        cout << vecMatrix[i].X << "X" << vecMatrix[i].Y << " ";
    }
    cout << endl;
}

int MinTimes(const vector<S_Matrix> & vecMatrix, int s, int e, vector<vector<int> > & vecRec, vector<vector<int> > & vecS)
{
    if (s == e) return 0;
    if (s < e && vecRec[s][e] > 0) return vecRec[s][e];

    int nMin = -1;
    int nK   = s;
    for (int i=s; i<e; ++i) {
        int nTimes = MinTimes(vecMatrix, s, i, vecRec, vecS) + MinTimes(vecMatrix, i+1, e, vecRec, vecS) + vecMatrix[s].X * vecMatrix[i].Y * vecMatrix[e].Y;
        if (nMin == -1) {
            nMin = nTimes;
            nK   = i;
        } else if (nMin > nTimes) {
            nMin = nTimes;
            nK   = i;
        }
    }
    vecRec[s][e] = nMin;
    vecS[s][e]   = nK;

    return nMin;
}

int MinTimes2(const vector<S_Matrix> & vecMatrix)
{
    int N = vecMatrix.size();
    vector<vector<int> > vecRec(N, vector<int>(N, 0));
    vector<vector<int> > vecS(N, vector<int>(N, -1));

    return  MinTimes(vecMatrix, 0, N-1, vecRec, vecS);
}

void PrintOptimalParens(const vector<vector<int> > & vecS, int i, int j) 
{
    if (i == j)
        cout << "A[" << i << "]";
    else {
        cout << "( ";

        PrintOptimalParens(vecS, i, vecS[i][j]);
        PrintOptimalParens(vecS, vecS[i][j]+1, j);

        cout << " )";
    }
} 

int OutPutMatrix(const vector<S_Matrix> & vecMatrix) 
{
    int N = vecMatrix.size();
    vector<vector<int> > vecRec(N, vector<int>(N, 0));
    vector<vector<int> > vecS(N, vector<int>(N, -1));

    MinTimes(vecMatrix, 0, N-1, vecRec, vecS);

    PrintOptimalParens(vecS, 0, N-1);
    cout << endl;
}

int main(int argc, char ** argv)
{
    vector<S_Matrix> vecMatrix = {
        S_Matrix( 30 , 35 ),
        S_Matrix( 35 , 15 ),
        S_Matrix( 15 , 5  ),
        S_Matrix( 5  , 10 ),
        S_Matrix( 10 , 20 ),
        S_Matrix( 20 , 25 ),
    };

    cout << "输入:";
    OutputMatrixVec(vecMatrix);
    
    cout << "最少计算的乘法次数:" << MinTimes2(vecMatrix) << endl;

    cout << "输出:";
    OutPutMatrix(vecMatrix);
    
    return 0;
}

代码我没有使用《算法导论》上的代码，主要原因是，书山的代码并不好理解，但是，书上的代码是精炼的，如果可以，我希望我有一天能把书上的代码编辑一边！
递归这种思维模式很适合数学公式的编写。尤其是通项公式。但是，递归的转化也是计算机的一种任务，不过递归所代码的代码开销在未来的计算机上会越来越小，所以，递归的编写方式是基本的，必须要掌握～