区间dp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int f[N][N], s[N], p[N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++){//前缀和
cin >> s[i];
p[i] = p[i - 1] + s[i];
}
/*
根据区间长度从小到大进行遍历
for(int len = 2; len <= n; len ++) //合并区间后的长度之和 确保区间合并的时候,较小的区间的min一定是确定的
{
for(int i = 1; i + len - 1 <= n; i ++)
{
int l = i, r = i + len - 1;
int w = p[r] - p[l - 1];
int res = 2e9;
for(int k = l; k < r; k ++)
//合并区间的代价: 左边的min + 右边的min + 总代价
res = min(res, f[l][k] + f[k + 1][r] + w);
f[l][r] = res;
}
}
*/
for(int i = n - 1; i >= 1; i --) //从后往前遍历,从而满足小区间都是确定已知的
// i从n-1开始 确保区间长度 >= 2
for(int j = i + 1; j <= n; j ++)
{
int w = p[j] - p[i - 1];
f[i][j] = 2e9;
for(int k = i; k < j; k ++)
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + w);
//这里的 i<= k < j <= n
//因为上一次循环中k>=i+1 所以所有的f[i][k] f[k][j]都已经计算过
}
cout << f[1][n] << endl;
return 0;
}
记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int f[N][N], s[N], p[N];
int n;
int merge(int l, int r)
{
if(l == r) return 0;
if(f[l][r]) return f[l][r];
int w = p[r] - p[l - 1];
f[l][r] = 1e9;
for(int k = l; k < r; k ++)
f[l][r] = min(f[l][r], merge(l, k) + merge(k + 1, r) + w);
return f[l][r];
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++){//前缀和
cin >> s[i];
p[i] = p[i - 1] + s[i];
}
cout << merge(1, n) << endl;
return 0;
}