区间dp

并不困难，这一类问题我的思通常是这样的：
关注最终状态。
我注意到了，最终只会剩一个元素。那么我们可以枚举这最后剩的一个元素。
决定了最后剩的元素就帮助我们把整个区间化成了两个小区间了。
类似分治了。

下面就是愉快的区间dp了

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 1e9;
int dp[110][110],a[110],n;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i)scanf("%d",&a[i]);
    for (int i=1;i<=n;++i)for (int j=i+2;j<=n;++j)dp[i][j]=inf;
    for (int p=3;p<=n;++p)
        for (int i=1,j=i+p-1;j<=n;++i,++j)
            for (int k=i+1;k<j;++k)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[k]*a[i]*a[j]);
    printf("%d\n",dp[1][n]);
}