矩阵链相乘

问题描述：
利用标准矩阵乘法计算矩阵 M₁, M₂, M₃ 之和，假设维数分别为2 * 10， 10 * 2， 2 * 10。那么(M₁M₂)M₃ = 2 * 10 * 2 + 2 * 2 * 10 = 80, 而M₁(M₂M₃) = 2 * 10 * 10 + 10 * 2 * 10 = 400, 次数相差5倍。如何快速地求出最少的次数？

---

矩阵链M_{i, j-1} = M_i * ··· * M_j-1， M_{j, k} = M_j * ··· * M_k
M_{i, k} = M_{i, j-1} + M_{j, k} + r_ir_jr_k+1(因为两个矩阵相乘的次数等于（第一个矩阵的行数 * 列数) * 第二个矩阵的列数）

所以有一个递推式：
C[i, k] = min{C[i, j-1] + C[j, k] + r_ir_jr_k+1} （i <= j <= k）

i 与 k 相乘， 它们之中有 k - i 种组合方式。

对于n个矩阵，为了减少重复计算，我们可以用一张n*n的表来记录 C[i, j] 的值，我们最终要得到得到值是C[1, n]。事实上，自底向上地填表可以避免重复计算。

代码示例：

#include <iostream>
#include <iomanip>
#include <memory.h>
using namespace std;

int N = 21;
int C[21][21];

struct Matrix
{
    int col; // 行
    int row; // 列
    friend istream& operator>>(istream& cin, Matrix& m);
};

Matrix* mat = 0;

istream& operator>>(istream& cin, Matrix& m)
{
    cin>>m.row>>m.col;
    return cin;
}

int theMin(int i, int j)
{
    int tmp = 0;
    int ans = 600000;
    for(int x = i; x < j; x++) {
        tmp = C[i][x] + C[x+1][j] + mat[i-1].row * mat[x-1].col * mat[j-1].col; // 数组从0开始，当然不用0号也可以
        if (tmp < ans) {
            ans = tmp;
        }
    }

    return ans;
}

void output()
{
    int N = 6;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            cout<<setw(6)<<C[i][j]<<" ";
        }
        cout<<endl;
    }
}


int main()
{
    // 不进行合法性检查。请保证输入合理
    int n;
    cin>>n;
    mat = new Matrix[n];
    memset(C, 0, N * N * sizeof(int));
    for (int i = 0; i < n; i++) {
        cin>>mat[i];
    }

    // 因为所有长为2的链，都是由长度为1的链的结果求出的，所有长为3的链，是由长为2的链的结果求出的，所以从长为1的链开始
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j + i > n) {
                break;
            }
            C[j][j+i] = theMin(j, j+i);
        }
    }

    cout<<"theMin: "<<C[1][n];
    cout<<endl;

    output();

    return 0;
}