区间DP

1、思路

2、代码模板：

#include<iostream>
#include<cstring>
using namespace std;

const int N=330;
const int INF=0x3f3f3f3f;

int n,s[N];
int f[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)//求前缀和
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }
    
    for(int len=2;len<=n;len++)//从小到大增加区间长度
    {
        for(int l=1;l+len-1<=n;l++)//对于每个区间长度len，从第一个点开始更新，l为区间的左端点
        {
            int r=l+len-1;//r代表区间的右端点
            f[l][r]=INF;  //刚开始让区间和为最大值
            for(int k=l;k<r;k++)//枚举左边堆的个数
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);//比较更新最小值
        }
    } 
    printf("%d",f[1][n]);
    return 0;
}