方法1 记忆化搜索

/**
 * 第一眼看到感觉和哈夫曼树好像啊，结果发现这个是连续的区间，不能隔着合并，我想多了。
 * 
 * 区间dp一般用记忆化搜索写，或者叫做动态规划的递归写法来进行书写，这样很方便，如果用循环写，这个题还可以，不是特别复杂
 * 但是同样的类似区间dp的滑雪那个题如果用循环来写。。。
 *
 * 定义集合：f(i,j) 表示合并i和j这个区间的代价的最小值，那么考虑上一个状态(一般都是找紧挨着的上一个状态)，也就是合并i，j的上一步，也就是当i，j区间是有两段的
 * 时候，所以我们也就得到了转移式子：f(i,j)=min(f(i,i)+f(i+1,j),f(i,i+1)+f(i+2,j).....)
 * 
*/
import java.util.*;
public class  Main{
    static int N;
    static int[] s=new int[301];//前缀和数组
    static int[] arr=new int[301];
    static int[][] f=new int[301][301];
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        //这个题需要初始化，因为记忆化搜索要知道某个状态是否被访问过
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) f[i][j]=-1;
        for(int i=1;i<=N;i++){
            arr[i]=sc.nextInt();
            s[i]=s[i-1]+arr[i];
        } 
        System.out.println(dp(1,N));
    }
    public static int dp(int i,int j){
        if(i==j){
            f[i][j]=0;
            return f[i][j];
        }
        if(f[i][j]!=-1) return f[i][j];
        f[i][j]=0x3f3f3f3f;
        for(int k=i;k<j;k++){
            f[i][j]=Math.min(f[i][j],dp(i,k)+dp(k+1,j)+s[j]-s[i-1]);
        }
        return f[i][j];
    }
}

方法2：for循环动态规划

先遍历长度，从长度为2开始遍历，长度为1的时候是初值0

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int [] st=new int[n+1];
        int[] q=new int[n+1];
        for(int i=1;i<=n;i++) st[i]=sc.nextInt();
        for(int i=1;i<=n;i++) q[i]=q[i-1]+st[i];
        int[][] f=new int[n+1][n+1];
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int l=i,r=i+len-1;
                f[l][r]=0x3f3f3f3f;
                for(int k=l;k<r;k++){
                    f[l][r]=Math.min(f[l][r],f[l][k]+f[k+1][r]+q[r]-q[l-1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}