区间dp

dp[i][j]表示将第 i 堆石子到第 j 堆石子合并成一堆的得分最小值，dp[1][n]即为最终结果。
注意枚举时先从区间长度len从小到大枚举，再枚举区间起点l，区间终点可以随之确定，r=l+len-1,
然后在每个区间中枚举k, k表示最终合并后的位置，即合并区间[l,r],可以看做先合并[l,k]和[k+1,r],再将这两堆合并，可以得到状态转移方程为：
$dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);$(s[]为前缀和数组)

时间复杂度$O(n^3)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[110];
int s[110];//前缀和
int dp[110][110];//将第i堆石子到第j堆石子合并成一堆的得分最小值，dp[1][n]即为答案
int main(){
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){//区间长度从小到大枚举
        for(int i=1;i+len-1<=n;i++){//枚举起点
        int l=i;
        int r=i+len-1;
        dp[l][r]=1e8;
            for(int k=l;k<r;k++){
                //设k为最终合并后的位置
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout <<dp[1][n];
    return 0;
}