C++ 石子合并（详细注释）

//算法思想：具有明显的阶段性（相邻的合并），所以只能区间dp，不能贪心。
//1.状态表示：f[i][j] 表示将 i 到 j 合并成一堆的方案的集合，属性 Min

//2.状态计算：枚举最后一个状态，k表示最后一次划分的位置(s数组用来存储前缀和)
//(1)i<j时，f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1])
//(2)i==j时，f[i][j]=0
//答案： f[1][n]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

const int N=310;

int f[N][N];//f[i][j] 表示将 i 到 j 合并成一堆的方案的集合，属性 Min
int a[N],s[N];//数组s用来存储前缀和

int main(){

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

    memset(f,0x3f,sizeof(f));//初始化f数组为正无穷

    //枚举所有的区间对应的所有的划分方案（k在区间的任意位置）
    for(int i=n;i>=1;i--){
        for(int j=i;j<=n;j++){//这一步可以优化
            if(i==j) {  f[i][j]=0; continue;}
            else{
                for(int k=i;k<=j-1;k++)//枚举k表示最后一次划分的位置
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }

    cout<<f[1][n];//答案就是f[1][n]

    return 0;
}