本题为入门的区间dp问题，

区间dp通常使用在：

1. 合并：即将两个或多个部分进行整合，当然也可以反过来；
2. 特征：能将问题分解为能两两合并的形式；
3. 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

这题在合并的时候，设$f[i][j]$为区间i到j合并后的最小结果。

$i$到$j$合并最小，自然是$i$到$k$，$k+1$到$j$合并了最小。

转移方程：$f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])$（$sum$为前缀和）

区间$dp$一般为三层循环，外层枚举区间长度

内层枚举区间起点，最内层枚举中间点$k$。

#include<bits/stdc++.h>
using namespace std;
int n,a[305],f[305][305],sum[305];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin>>n;
	memset(f,0x3f,sizeof(f));//初始化无穷大
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		f[i][i]=0;//自己合并花费0
	}
	for(int len=2;len<=n;len++) //枚举区间长度 
    //从2开始，因为1已经初始化了
	{
		for(int i=1;i<=n-len+1;i++)//枚举左端点 
		{
			int j=i+len-1;//右端点 
			for(int k=i;k<j;k++)//保证k+1小于等于j
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
			}
		}
	}
	cout<<f[1][n];
    return 0;
}