$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. f[i][j] 表示合并区间 [i,j] 的最小代价
2. 依次枚举长度 len，起点 i，分界点 k
3. 状态转移方程：f[i][j] = min{f[i][k] + f[k+1][j] + s[j] - s[i-1]} (i <= k < j)

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N]; //合并区间[i,j]的最小代价

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }

    for(int len=2;len<=n;len++) //枚举长度
        for(int l=1;l+len-1<=n;l++) //枚举起点
        {
            int r=l+len-1; //起点，终点
            f[l][r]=0x3f3f3f3f;
            for(int k=l;k<r;k++) //枚举分界点
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }

    cout<<f[1][n]<<endl;

    return 0;
}