$f[i,j]$表示$[i,j]$的最优，用记忆化比较好写。

至于算的部分暴力就好，反正$O(n^4)$不虚，上界达不到。

或者前缀和$O(n^3)$。

# include <stdio.h>
# include <algorithm>
using namespace std;
bool v[120][120];
int n, a[120], f[120][120];
int calc(int l,int r) {
	int res = 0;
	for (int i=l; i<=r; ++i) res += a[i];
	return res;
}
int get(int l,int r) {
	if (v[l][r]) return f[l][r];
	int minn=9009999;
	for (int i=l;i<r;++i) 
		minn = min(minn, get(l,i)+get(i+1,r)+calc(l,r));
	v[l][r]=1;
	return f[l][r]=minn;
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			f[i][j]=9009999;
	for (int i=1;i<=n;++i) {
		f[i][i]=0; v[i][i]=1;
		if (i!=n) f[i][i+1]=a[i]+a[i+1], v[i][i+1]=1;
	}
	printf("%d\n",get(1,n));
	return 0;	
}