区间DP
$ 时间复杂度O(N^3),空间复杂度O(N^2)$
参考文献
算法基础课
AC代码
#include <iostream>
using namespace std;
const int N = 310;
int n;
int a[N], s[N];
int f[N][N];
int main(){
//读入,并初始化前缀和
cin >> n;
for (int i = 1 ; i <= n ; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
//枚举区间长度
for (int len = 2 ; len <= n ; len ++){
//枚举左端点和右端点
for (int i = 1 ; i + len - 1 <= n ; i ++){
int j = i + len - 1;
f[i][j] = 1e9;
for (int k = i ; k < j ; k ++){
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n];
return 0;
}