5、区间DP &石子合并

AcWing 282. 石子合并

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 310;
    int a[] = new int[N];
    int s[] = new int[N];
    int n;
    int f[][] = new int[N][N];


    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            s[i] = s[i - 1] + a[i];
        }
        //f[i][j]所有从【第i到第j堆】石子合并成一堆的合并方式

        //先求小区间：[1,2] [2,3] [3,4] [4,5] ......
        //再求大区间：[1,3] [2,4] [3,5] ....
        //再求大大区间：[1,4] [2,5] ...
        //再求大大大区间：[1,5]
        for (int length = 1; length <= n; length++) {
            for (int i = 1; i < n; i++) {
                int j = i + length;
                if(j<=n){
                    f[i][j] = (int) 1e9;
                    for (int k = i; k <= j - 1; k++) {
                        f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                    }
                }
            }
        }
        System.out.println(f[1][n]);
    }
}