想出状态转移方程容易,如下:
- f[i][j]表示合并a[i…j]位置上的石子所需要的代价
- f[i][j] = min(f[i][k] + f[k+1][j]) + sum[i…j], i<=k<j
但是要写程序就不容易了,因此f[i][j]
的状态由f[i][k]和f[k+1][j]
决定,因此枚举顺序可选择按照区间长度来枚举,写起来易出错。这样的题用记忆化搜索就很简单啦,就不需要考虑上述问题,代码如下:
// 区间dp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int a[N], sum[N];
int f[N][N];
// f[i][j]表示合并a[i...j]位置上的石子所需要的代价
// f[i][j] = min(f[i][k] + f[k+1][j]) + sum[i...j], i<=k<j
void dfs(int i, int j)
{
if(i == j) {
f[i][j] = 0;
return;
}
if(f[i][j] != -1) return;
int ret = 1e9;
for(int k = i; k < j; k ++ ){
dfs(i, k);
dfs(k + 1, j);
ret = min(ret, f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
}
f[i][j] = ret;
}
int main()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + a[i];
memset(f, -1, sizeof f);
dfs(1, n);
cout << f[1][n] << endl;
return 0;
}