思路很清晰：对于dp[i][j]代表以第i个为起始，第j个为结束的最优组合方式，每一次对于其中的一个k进行操作即可。
还有就是对于环状关系的简便存储方式，只是记得改2*n个点而不是n个。
代码：
#include<cstdio> #include<iostream> using namespace std; #define maxn 200 int a[maxn],dp[maxn][maxn],n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } for(int i=2;i<=n+1;i++) { for(int l=1;l+i<=2*n;l++) { int r=l+i; for(int k=l+1;k<r;k++) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]); } } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i][i+n]); printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/10122365.html