题目描述
blablabla
JAVA 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 310;
static int[] a = new int[N];
static int[][] f = new int[N][N];//f[i][j]表示将所有[i-j]合并成一堆的方案集合,取最小值
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(s[i-1]);
a[i] += a[i-1];//区间和
}
//套路:先枚举区间长度
for (int len = 2; len <= n; len++) {//从2开始
for (int i = 1; i + len -1 <= n; i++) {//枚举左区间,减一是左区间最多到n-1,然后右区间留一个
int j = i + len -1;
f[i][j] = (int) 1e8;
for (int k = i; k < j; k++) {//k最多到j-1,
f[i][j] = Math.min(f[i][j],f[i][k] + f[k+1][j] + a[j] - a[i-1]);
}
}
}
System.out.println(f[1][n]);
}
}