【问题描述】给定n个矩阵M1,M2…Mn，他们的维数分别是r1c1,r2c2…rn*cn，要求使用【动态规划】的策略求解矩阵连乘的最优计算代价(总乘法次数最少)。题目保证矩阵相乘一定是有效的。

例如有三个矩阵M1，M2，M3，他们的维度分别是210,102，210。按照矩阵乘法的结合律，可以先把M1和M2相乘，然后把结果和M3相乘，总的乘法次数为2102+2210=80次；也可以先把M2和M3相乘，再用M1去相乘，这种方式下总的乘法次数为10210+210*10=400次。因此最优计算代价为80。
【输入形式】输入的第1行中有1个数字n，表示矩阵的个数；接下来n行，每行2个整数ri和ci，分别表示矩阵Mi的行数和列数。
【输出形式】输出1行中有一个数字，表示n个矩阵相乘的最优计算代价。
【样例输入】

3

2 10

10 2

2 10
【样例输出】

80

矩阵链，求最小乘法次数
DP:
1.状态表示:
1.1 集合：f[i][j] : 表示从矩阵Mi 到矩阵Mj （i<j）的相乘次数
1.2 属性：Min
2 状态计算:Ai…j = Ai…k * Ak+1 …j
枚举区间长度 len from 2 to n
将f[i][j]划分为 i i+1 … k … j-1子集和 k从i枚举到j-1
f[i][j] = min(f[i][k] + f[k+1][j] + p[i-1]p[k]p[j] ,f[i][j])

#include<bits/stdc++.h>
using namespace std;
const int N = 110;

int main()
{
    int n, f[N][N];
    int p[N];
    cin>>n;
    for(int i = 1 ; i <= n ; i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        p[i-1] = a ; p[i] = b;
    }
    for(int len = 2 ; len <= n; len ++)
    {
        for(int i = 1; i <= n - len + 1 ; i ++)
        {//j - i + 1 = len
            int j = i + len -1;
            f[i][j] = 1e9;
            for(int k = i; k <= j - 1; k ++)
            {
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}