石子合并（区间动态规划）- NYOJ 737
描述
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据，输入到文件结束。 每组测试数据第一行有一个整数n，表示有n堆石子。 接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出
输出总代价的最小值，占单独的一行
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239
思路：
若没有要求将相邻的两堆石子堆成一堆，那么那么我们可以把n堆石子放入一个优先队列，每次取出最小的两堆，合并后压入优先队列，直到队列中只有一堆为止。
题目要求合并的过程只能每次将相邻的两堆石子堆成一堆，所以使用区间动态规划来解决。
即若要求一个大的区间的最优解，先求小区间的最优解，然后小区间慢慢的推出大区间的最优解。
核心部分就是三层for循环，第一层枚举区间的长度，第二层枚举起点的位置，第三层枚举最后一次合并的位置。
例如：
要求1~5这个区间，用dp[1][5]来形容1~5的最优值，那么dp[1][5]肯定为dp[1][1]+dp[2][5],dp[1][2]+dp[3][5], dp[1][3]+dp[4][5] ,d[1][4]+dp[4][5]这个四个值里面最小的一个，而这些子区间肯定是由更小的子区间组成的，所以应该一步一步推，先求小子区间最优解，最后求出dp[1][n]。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
//#define inf 1<<20
const int maxn = 210;
int n, a[maxn];
int dp[maxn][maxn];
//dp[i][j]表示从第i堆到第j堆合并的代价
int sum[maxn][maxn];//表示石头的数量
int main()
{
ios::sync_with_stdio(0);
while (cin >> n)
{
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(sum, 0, sizeof(sum));
//fill(dp[0],dp[0]+n*n,inf);//错误
fill(dp[0], dp[0] + maxn * maxn, inf); //fill填充量必须是常数
for (int i = 1; i <= n; i++)
sum[i][i] = a[i], dp[i][i] = 0;
for (int len = 1; len < n; len++) { //区间长度
for (int i = 1; i <= n && i + len <= n; i++) { //区间起点
int j = i + len; //区间终点
for (int k = i; k <= j; k++) //用k来表示分割区间
{
sum[i][j] = sum[i][k] + sum[k + 1][j];
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
}
}
}
cout << dp[1][n] << endl;
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-05-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读