問題描述：
利用標(biāo)準(zhǔn)矩陣乘法計(jì)算矩陣 M₁, M₂, M₃ 之和，假設(shè)維數(shù)分別為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, 次數(shù)相差5倍。如何快速地求出最少的次數(shù)？

矩陣鏈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(因?yàn)閮蓚€(gè)矩陣相乘的次數(shù)等于（第一個(gè)矩陣的行數(shù) * 列數(shù)) * 第二個(gè)矩陣的列數(shù)）

所以有一個(gè)遞推式：
C[i, k] = min{C[i, j-1] + C[j, k] + r_ir_jr_k+1} （i <= j <= k）

i 與 k 相乘， 它們之中有 k - i 種組合方式。

對(duì)于n個(gè)矩陣，為了減少重復(fù)計(jì)算，我們可以用一張n*n的表來記錄 C[i, j] 的值，我們最終要得到得到值是C[1, n]。事實(shí)上，自底向上地填表可以避免重復(fù)計(jì)算。

代碼示例：

#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; // 數(shù)組從0開始，當(dāng)然不用0號(hào)也可以
        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()
{
    // 不進(jìn)行合法性檢查。請(qǐng)保證輸入合理
    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];
    }

    // 因?yàn)樗虚L(zhǎng)為2的鏈，都是由長(zhǎng)度為1的鏈的結(jié)果求出的，所有長(zhǎng)為3的鏈，是由長(zhǎng)為2的鏈的結(jié)果求出的，所以從長(zhǎng)為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;
}