状态定义为删除两处之间所有数的dp

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 const int INF=0xffffff;
 6 
 7 const int maxn=105;
 8 int a[maxn];
 9 int dp[maxn][maxn];
10 
11 int ddp(int i,int j)
12 {
13     if(dp[i][j]!=-1)
14     return dp[i][j];
15     if(j-i<=1)
16     return dp[i][j]=0;
17     int ans=INF;
18     for(int k=i+1;k<=j-1;k++)
19     {
20         int x=ddp(i,k)+ddp(k,j)+a[i]*a[k]*a[j];
21         if(ans>x)
22         ans=x;
23     }
24     return dp[i][j]=ans;
25 }
26 
27 int main()
28 {
29     int n;
30     //freopen("aa.txt","r",stdin);
31     while(scanf("%d",&n)!=EOF)
32     {
33         memset(dp,-1,sizeof(dp));
34         for(int i=0;i<n;i++)
35         scanf("%d",&a[i]);
36         printf("%d\n",ddp(0,n-1));
37     }
38     return 0;
39 }