状态表示 $f[i][j]$ (化整为零)
$f[i][j]$表示集合
通过一个二维数组来表示所有将第$i$堆石子到第$j$堆石子合并为一堆石子的合并方式

属性：所有合并方式代价的最小值$（min）$

状态计算——集合的划分（化零为整）

将集合划分为$i-k+1$个集合
对于集合$f[i][j]$我们将其同样划分为：

以最后一次分界线的位置将集合分为很多类

• 当分界线在第一堆石子后边时
• 当分界线在第二堆石子后边时
• . . . . . .
• 当分界线在第$k$堆石子后边时
• . . . . . .
• 当分界线在第$j-1$堆石子后边时

当分界线在第$k$堆石子后边时
此时将区间$[l,r]$分为$[l,k]$和$[k+1,r]$两部分
将这两个区间看作为以及合并好的两堆石子
最后合并时的代价是$f[l][k]+f[k+1][r]+s[r]-s[l-1]+1$

状态转移方程：

$\color{red}{f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1])}$

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N = 310; //数据范围300
int s[N]; //前缀和数组
int f[N][N]; //f[i][j]表示从第i堆石子到第j堆石子合并为一堆石子的最小代价

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);

    for(int i=1;i<=n;i++) s[i]+=s[i-1]; //前缀和初始化

    for(int len = 2;len <= n;len ++) //枚举区间长度
    {
        for(int i=1;i + len - 1<=n;i++) //枚举区间长度下对应的左端点
        {
            int l = i,r = i + len -1; //枚举区间的左右端点
            f[l][r]=1e8;
            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; //输出从第一堆石子到第n堆石子合并为一堆石子的最小代价

    return 0;
}