题意：除了头尾不能动，每次取出一个数字，这个数字与左右相邻数字的乘积为其价值，最后将所有价值加起来，要求最小值
和最优矩阵链乘模型一样，最后取出的数决定了序，，如果没学过最优矩阵连乘找重复子问题还是比较难找的
DP
//180K0MS#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int dp[110][110];int n;int num[110];void debug(){for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++) printf("%6d",dp[i][j]);}int main(){while(~scanf("%d",&n)){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int l=1;l<=n;l++)for(int p=1;p<=n;p++)if(p+l<=n)for(int k=p+1;k<p+l;k++)dp[p][p+l]= k==p+1? dp[p][k]+dp[k][p+l]+num[p]*num[k]*num[p+l]:min(dp[p][p+l],dp[p][k]+dp[k][p+l]+num[p]*num[k]*num[p+l]) ;// debug();printf("%d\n",dp[1][n]);}return 0;}记忆化的思路清晰一点：
//180K0MSC++617B#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n;int dp[110][110],num[110];int morize(int l,int r){int &ans=dp[l][r];if(ans>=0) return ans;if(l+1==r) return ans=0;for(int k=l+1;k<r;k++)ans= k==l+1? morize(l,k)+morize(k,r)+num[l]*num[k]*num[r] : min(ans,morize(l,k)+morize(k,r)+num[l]*num[k]*num[r]);return ans;}int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++) scanf("%d",&num[i]);memset(dp,-1,sizeof(dp));printf("%d\n",morize(1,n));}return 0;}
继续期待我的下一个旅行，拿起背包，
