矩阵链乘最小代价

先来聊聊思路，首先预备知识是矩阵的相乘，若暂时没学过，那得看看矩阵是如何做乘法的。

假设我们已经知道矩阵是如何相乘的，那么然后我们可以从一个实例出发：有四个矩阵，为了偷懒我们给它们取名为：A1，A2，A3，A4。
其中：

    A1为4行5列的矩阵
    A2为5行7列的矩阵
    A3为7行3列的矩阵
    A4为3行9列的矩阵

我们有很多种做乘法的方式，例如：（（（A1A2）A3）A4）等，就不一个一个列举了。回到这个问题，（（（A1A2）A3）A4）的乘法次数为多少？
我们应该好好想一想，因为只有理解问题是什么，我们才能更好地解决问题。
下面我直接给一个答案，（（（A1A2）A3）A4）的乘法次数为：332（如果我没算错的话，否则请狠狠地批评我！）
然后直接说最优的乘法次数吧，在这个例子中最优的其中一种情况是：273。关于这个解我们是这样得到的：（（A1（A2A3））A4）
说了这么多废话，只想说明一件事，那就是多个矩阵做乘法有很多种计算方式，但是每种方式不一定都是一样的乘法代价（有时候可能同样的矩阵链乘的代价相差极大），因此就有了矩阵链乘最小代价这个问题。

代码如下：

//注意：本题中当前最优是基于前面子部分最优（因此必须确保前面的结果已经得到最优）
//一个形象的例子是：要建成n层楼必须先建好前面的n-1层楼（即自底向上）
#include <iostream>
using namespace std;
int n;
//P：矩阵维数、M[i][j]：矩阵Ai——Aj的最小代价、T[i][j]：矩阵Ai——Aj的断开位置
int P[1001],M[1001][1001],T[1001][1001];
void solve()
{
    for(int i = 1;i <= n;++i)
        M[i][i] = 0;                                                                             
    for(int i = 1;i < n;++i)    //可以把i理解成步长                                             
    {
        for(int j = 1;j < n-i+1;++j)
        {
            int q = j+i;         //最开始选择的是连续两个矩阵，下一次选择连续三个矩阵，同理后面每次递增1                                                                      
            M[j][q] = 219999999;    //矩阵Aj——Aq的最小代价（初始为无穷大，同时注意j和q的取值）
            for(int k = j;k < q;++k)    
            {
                int t = M[j][k]+M[k+1][q]+P[j-1]*P[k]*P[q]; //t=min(M[j][k]+M[k+1][q]+P[j-1]*P[k]*P[q], t)(j<=k<q)
                if(t < M[j][q])    //与上面注释的公式相对应
                {
                    M[j][q] = t;    
                    T[j][q] = k;                                 //保存矩阵Aj——Aq的断开位置
                }
            }
        }
    }
}
void path(int i,int j)
{
    if(i==j)      //此时Ai——Aj已经不能再断开成两部分了
    {
        cout << "A" << i;
        return;
    }
    else
    {
        cout << "(";
        path(i,T[i][j]);     //Ai——Aj从k处断开成两部分（感到疑惑请看前面所定义的T[i][j]的含义）
        path(T[i][j]+1,j);
        cout << ")";
    }
}
int main(void)
{
    cin >> n;//矩阵个数
    for(int i = 0;i <= n;++i)
        cin >> P[i];
    solve();
    cout << M[1][n] << endl;
    path(1,n);
    return 0;
}

在这段程序中，假如有四个矩阵A，B，C，D。
我们先算出的是（AB），（BC），（CD）的最优代价（因为只有两个矩阵相乘，因此最小代价就为它们相乘）
然后算出（ABC），（BCD）的最优代价。对于（ABC），因为我们已经知道（AB）和（BC）的最小代价，所以(ABC) 的最小代价= min{A(BC),(AB)C}；对于（BCD）同理。
最后算出（ABCD）的最优代价，同样我们知道（ABC）、（AB）、（CD）、（BCD），所以（ABCD）的最小代价=min{A(BCD),(AB)(CD),(ABC)D}。