题意：

合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

思路：

核心：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

状态表示：f[i][j] 表示将 i 到 j 合并成一堆的方案的集合，属性 Min

状态计算：
(1)i<j时，i<=j<i+len−1 f[i][j]=min(f[i][i+len-1],f[i][j]+f[j+1][i+len-1]+s[i+len-1]−s[i−1]
问题答案： f[1][n]

区间 DP 常用模版

所有的区间dp问题，第一维都是枚举区间长度，一般 len = 1 用来初始化，枚举从 len = 2 开始，第二维枚举起点 i （右端点i + len - 1）

for(int len=2;len<=n;len++)             //区间长度
{
    for(int i=1;i+len-1<=n;i++)         //枚举起点
    {
        f[i][i+len-1]=1e9;
        for(int j=i;j<i+len-1;j++)      //枚举分段点，构造状态转移方程
        {
            f[i][i+len-1]=min(f[i][i+len-1],f[i][j]+f[j+1][i+len-1]+s[i+len-1]-s[i-1]);
        }
    }
}

代码

#include<iostream>
using namespace std;
const int N=310;
int a[N],s[N];//s[n]用来记录前缀和
int f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            f[i][i+len-1]=1e9;
            for(int j=i;j<i+len-1;j++)
            {
                f[i][i+len-1]=min(f[i][i+len-1],f[i][j]+f[j+1][i+len-1]+s[i+len-1]-s[i-1]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}