这题题意看上去和合并果子 那题很相似，合并果子是贪心问题，用小根堆做，把最小的合并就行。

思路

区别在于此题：每次只能合并相邻的两堆,区间DP
最后一步是合并两堆，枚举[L,R]区间上两堆的分界点k,k的取值范围是[L,R-1]
f[L][k]+f[k+1][R]+S[R]-S[L-1]

做此题过程中出现的一些问题，需要注意：
1.f[i][j]因为是求min,故初始化一般为正无穷，但此次不能初始化为Integer.MAX_VALUE,因为f[l][k]+f[k+1][r]+S[r]-S[l-1]会导致int类型溢出，计算机得出的结果就是负数了。故此处初始化为0x3f3f3f3f
2.对二维矩阵进行初始化的操作，最开始采用的是
int[] tmp=new int[N]; Arrays.fill(tmp,INF); Arrays.fill(f,tmp);
但是这种初始化的方式会出错，值一直不对，不采用，改成直接对f[i][j]赋值。
3.循环枚举求解f[l][r]
此处不能通过枚举左右边界进行循环
因为这样f[k+1][r]会导致当前的f[l][r]计算的晚，故其中为初始化的值0；

//错误的写法
        for(int l=1;l<=n;l++){
            for(int r=l;r<=n;r++){
                for(int k=l;k<=r-1;k++){
                    f[l][r]=Math.min(f[l][r],f[l][k]+f[k+1][r]+S[r]-S[l-1]);
                }
            }
        }

代码

import java.util.*;
class Main{
    static int INF=0x3f3f3f3f;
    static int N=310;
    static int[] S=new int[N];
    static int[][] f=new int[N][N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=1;i<=n;i++){
            S[i]=S[i-1]+sc.nextInt();
            f[i][i]=0;
        }
        //枚举区间长度，保证f[k+1][r]中已经有值
        //且符号题意，先去计算原始的俩堆合并的结果，再计算合并后的两堆
        //区间长度从2开始，因为堆大小为1的时候，不用合并，代价为0，
        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                f[l][r]=INF;
                for(int k=l;k<=r-1;k++)
                    f[l][r]=Math.min(f[l][r],f[l][k]+f[k+1][r]+S[r]-S[l-1]);
            }
        }    
        System.out.print(f[1][n]);
    }
}