思路

状态转移方程

f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + (s[j] - s[i - 1));

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
int a[310],s[310];
int f[310][310];
int n;

int main(){
    cin >> n;
    memset(f,0x3f,sizeof f); //初始化
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; //计算前缀和
        f[i][i] = 0; //初始化
    }

    for(int len = 1; len < n; len ++){ //len 表示区间跨度
        for(int i = 1; i + len <= n; i ++){
            int j = i + len;  // i和j分别表示区间的左端点和右端点
            for(int k = i; k < j; k ++){
                f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + (s[j] - s[i - 1])); //状态转移方程
            }
        }
    }

    cout << f[1][n] << endl;
    return 0;
}