这是一道典型的区间动归

#include <bits/stdc++.h>
using namespace std;
int s[1001],f[1001][1001],n;
int dp(int l, int r) {
    if (l==r)return 0;
    if (f[l][r]!=INT_MAX)return f[l][r];
    for(int i=l;i<r;i++) {
        f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r)+s[r]-s[l - 1]);
    }
    return f[l][r];
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)f[i][j]=INT_MAX;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
    cout<<dp(1,n);
    return 0;
}