转：https://blog.csdn.net/c18219227162/article/details/50412333

思考：这里为什么能够枚举最后的分割点，因为矩阵乘法的性质：如果

以A3为分割点那么不管A1-A3通过什么顺序乘，得到的矩阵一定是A1(行)*A3(列)

同理：A4-A6最后得到的一定是A4(行)*A6(列)
而且A3(列)一定等于A4(行)。

所以最后一次乘法的次数一定为：A1(行) * A3(列) * A6(列)

所以我们只保存列数就行了。特别的保存P(0)=A1(行)

区间dp中k为最后一次操作的分割线，那么这个贡献是可以计的，下一篇博客会体现这个性质。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n;
int P[105];
int dp[105][105];
int dfs()
{
    for(int Len=2;Len<=n;Len++)
    {
        for(int L=1;L+Len-1<=n;L++)
        {
            int R=L+Len-1;
            dp[L][R]=10000000;
            for(int k=L;k<R;k++)
            {
                dp[L][R]=min(dp[L][R], dp[L][k]+dp[k+1][R]+P[L-1]*P[k]*P[R]);
            }
        }
    }

    return dp[1][n];
}

int main()
{
    memset(dp, 0, sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        if(i==1)
        {
            P[0]=x;
        }
        P[i]=y;
    }
    cout<<dfs()<<endl;

    return 0;
}