拿下

#include <iostream>
using namespace std;
int a[1005],s[1005],dp[1005][1005]; 
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	//区间动态规划思路   枚举 长度+左端点 
	for(int len=1;len<n;len++){//len 表示i和j下标的差值  
		for(int i=1;i+len<=n;i++){
			int j=i+len;//自动获得右端点
			 dp[i][j]=99999999;
			 for(int k=i;k<=j-1;k++){//满足k+1<=j 
			 	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
			 }
		}
	} 
	cout<<dp[1][n];
	return 0;
}