记忆化搜索写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 330;
int f[N][N], s[N];
int bestCost(int low, int high){
if(f[low][high] != -1)return f[low][high];
if(low == high){
f[low][high] = 0;
return f[low][high];
}
int best = 2e9;
for(int k = low; k < high; k ++){
int lowBest = bestCost(low, k);
int highBest = bestCost(k+1, high);
best = min(best, lowBest + highBest + s[high] - s[low-1]);
}
f[low][high] = best;
return f[low][high];
}
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> s[i];
}
for(int i = 1; i <= n; i ++)s[i] += s[i-1];
memset(f, -1, sizeof f);
int ans = bestCost(1, n);
cout << ans << endl;
return 0;
}
自底向上
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 330;
int f[N][N], s[N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> s[i];
}
for(int i = 1; i <= n; i ++)s[i] += s[i-1];
for(int len = 2; len <= n; len ++)
for(int low = 1; low <= n - len + 1; low ++){
int high = low + len - 1;
f[low][high] = 2e9;
for(int k = low; k < high; k ++){
f[low][high] = min(f[low][high], f[low][k] + f[k+1][high] + s[high] - s[low-1]);
}
}
cout << f[1][n] << endl;
return 0;
}