接下来就是区间dp
区间dp有个可以套模板，就是枚举区间长度，然后每个区间等于他的两个子区间相加最大/最小。。。
直接上例题。
最典型例题合并石子：http://120.78.128.11/Problem.jsp?pid=2385
直接枚举每个区间长度一层一层往上就好了，类似于归并排序。需要注意的是这个是一个环形的所以直接复制一圈就好了

#include<bits/stdc++.h>
using namespace std;
int a[705],sum[707]={0};
int dp[705][705];
int dfs(int ,int );
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[n+i]=a[i];
    }
    for(int i=1;i<=n+n;i++)sum[i]=sum[i-1]+a[i];
    //for(int i=1;i<=n+n;i++)dp[i][i]=a[i];
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n+n;l++){
            int r=len+l-1;
            dp[l][r]=1e9+1;
            for(int k=l;k<r;k++)dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
        }
    }
    int ans=1e9+1;
    for(int i=1;i<=n;i++)ans=min(ans,dp[i][i+n-1]);
    cout<<ans<<endl;
    system("pause");
    return 0;
}

例题二：http://120.78.128.11/Problem.jsp?pid=2384
和例题一一样直接套模板就好了，这个也是环形的，所以也需要复制一圈就好了

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,ans=0;
ll a[1010];
ll dp[400][400]={0};
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i+n+n]=a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=n+1;len+l-1<=n+n+n;l++){
            int r=l+len-1;
            dp[l][r]=0;
            for(int k=l;k<r;k++){
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l-1]*a[k]*a[r]);
            }
        }
    }
    for(int i=1;i<=n;i++)ans=max(dp[i+n][i+n+n-1],ans);
    cout<<ans<<'\n';
    return 0;
}