题目描述

石子合并

java 代码

import java.util.*;
import java.io.*;

class Main{
    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] = sc.nextInt();
        for(int i=1; i<=n;i++) s[i]+=s[i-1];

        //从2开始原因： 从1开始 -> 第一次代价都是0
        //这里的len 是能够分成 len 段 长度.
        for(int len=2; len<=n;len++){
            //i是左边能枚举的石子
            for(int i=1;i+len-1<=n;i++){

                int l=i, r=i+len-1;
                f[l][r] = 0x3f3f3f;
                for(int k=l; k<r;k++){
                    f[l][r] = Math.min(f[l][r], f[i][k]+ f[k+1][r]+ s[r]-s[l-1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}