C++ 代码

/*
区间dp定义
    f[i][j]：将从i到j堆石头合并的代价
    dp[i][j]：为min

f[i][j]可以划分种k状态(k=i ~~~~~ j-1),k为最后一次石头合并的分界线
     dp[i][j] = min(  dp[l][k] + dp[k+1][r]  )  k从l到r。
     仔细看就会发现当你计算dp[i][j]的时候，你所需要的是i j之间的一系列dp值
     所以写代码的时候，不能从for(int i = 0 *** ) for(j=0 ***)
     要先for(int len = 2 ; len <= n ; len++)，以长度为第一循环，因为dp[i][j]，需要j-i长度内 所有dp的值

*/

#include <bits/stdc++.h>
using namespace std ;
int n ; const int N = 310 ; int a[N],s[N],dp[N][N] ;
int main(){
    ios::sync_with_stdio(false);
    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 , r = i +len-1 ;  //左右端点
            dp[l][r] = 1e8;             
            for(int k = l ; k < r ; k++){ //
                dp[l][r] = min(dp[l][r] , dp[l][k] + dp[k+1][r] + s[r] - s[i-1]) ; 
            }
        }
    }
    cout<<dp[1][n];
    return 0 ;
}