Multiplication Puzzle POJ - 1651
区间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]);
}Kuangbin题单详解(区间dp) 文章被收录于专栏
lets go
