题目描述
区间DP:先枚举区间长度 再枚举左端点
前缀和+区间DP
//左边合并的代价 + 右边合并的代价 + 把左右两边合并的代价
f[i][k] + f[k + 1][j] + s[j] - s[i - 1]
import java.util.*;
//区间DP:先枚举区间长度 再枚举左端点
public class Main {
static final int N = 310;
static int n;
static int[] s = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
//预处理前缀和
for (int i = 1; i <= n; i++) {
s[i] = scanner.nextInt();
s[i] += s[i - 1];
}
//从长度为2的区间开始 区间为1 默认就不用合并 消耗为0
for (int len = 2; len <= n; len++) {
//枚举左端点
for (int i = 1; i + len - 1 <= n; i++) {
//就是右端点
int j = i + len - 1;
//先初始为无穷大
f[i][j] = Integer.MAX_VALUE;
//枚举k
for (int k = i; k < j; 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]);
}
}