石子合并问题 三种类型

一：任意版

有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。

此类问题比较简单，就是哈夫曼编码的变形，用贪心算法即可求得最优解。即每次选两堆最少的，合并成新的一堆，直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。

二：直线版

在一条直线上摆着N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。

如果熟悉矩阵连乘对这类问题肯定非常了解。矩阵连乘每次也是合并相邻两个矩阵（只是计算方式不同）。那么石子合并问题可用矩阵连乘的方法来解决。

那么最优子结构是什么呢？如果有N堆，第一次操作肯定是从n-1个对中选取一对进行合并，第二次从n-2对中选取一对进行合并，以此类推……

设best[i][j]表示i-j合并的最优值, sum[i][j]表示第i堆石子到第j堆石子的总数量，递推公式如下：

#include #include #include #include using namespace std;

#define MAXN 100 int sum[MAXN];

int best[MAXN][MAXN];

int n, stone[MAXN];

int getBest() {

//初始化，没有合并，花费为0 for(int i = 0; i < n; ++i) {

best[i][i] = 0; }

//还需进行合并次数

for(int v = 1; v < n; ++v) {

//每次合并都是一条对角线,i表示行

for(int i = 0; i < n - v; ++i)

{

//根据第v次合并，现在更新i行值可以求出列的值 int j = i + v;

best[i][j] = INT_MAX;

int add = sum[j] - (i > 0 ? sum[i - 1] : 0); //中间断开位置，取最优值

for(int k = i; k < j; ++k)

{

best[i][j] = min(best[i][j], best[i][k] + best[k + 1][j] + add); } } }

return best[0][n - 1]; }

int main() {

scanf(\

for(int i = 0; i < n; ++i) scanf(\

sum[0] = stone[0];

for(int i = 1; i < n; ++i) {

sum[i] = sum[i - 1] + stone[i]; }

int best = getBest(); printf(\ return 0; }

三：圆形版

如果石子是排成圆形，其余条件不变，那么最优值又是什么呢？

因为圆形是首尾相接的，初一想，似乎与直线排列完全成了两个不同的问题。因为每次合并后我们都要考虑最后一个与第一个的合并关系。直线版的矩阵连乘对角线式的最优子结构不见了。f(i, j)表示i-j合并的最优值似乎并不可行，因为我们可以得到的最优值第一步就是第一个与最后一个合并，那么f(i, j)并不能表示这种关系。

修改一下，f(i, j)表示从第i个开始，合并后面j个得到的最优值。sum(i, j)表示从第i个开始直到i+j个的数量和。那么这个问题就得到解决了。注意要把其看成环形，即在有限域内的

合并。

递推公式如下：

#include #include #include #include using namespace std;

#define MAXN 100 int sum[MAXN];

int mins[MAXN][MAXN], maxs[MAXN][MAXN];

int n, stone[MAXN];

int sums(int i, int j) {

if(i + j >= n) {

return sums(i, n - i - 1) + sums(0, (i + j) % n); } else {

return sum[i + j] - (i > 0 ? sum[i - 1] : 0); } }

void getBest(int& minnum, int& maxnum) {

//初始化，没有合并，花费为0 for(int i = 0; i < n; ++i)

{

mins[i][0] = maxs[i][0] = 0;

}

//还需进行合并次数

for(int j = 1; j < n; ++j)

{

for(int i = 0; i < n; ++i)

{

mins[i][j] = INT_MAX;

maxs[i][j] = 0;

for(int k = 0; k < j; ++k)

{

mins[i][j] = min(mins[i][k] + mins[(i + k + 1)%n][j - k - 1] + sums(i, j), mins[i][j]);

maxs[i][j] = max(maxs[i][k] + maxs[(i + k + 1)%n]

[j - k - 1] + sums(i, j), maxs[i][j]); } } }

minnum = mins[0][n - 1]; maxnum = maxs[0][n - 1]; for(int i = 0; i < n; ++i)

{

minnum = min(minnum, mins[i][n - 1]); maxnum = max(maxnum, maxs[i][n - 1]); } }

int main() {

scanf(\

for(int i = 0; i < n; ++i) scanf(\

sum[0] = stone[0]; for(int i = 1; i < n; ++i) {

sum[i] = sum[i - 1] + stone[i]; }

int minnum, maxnum;

getBest(minnum, maxnum);

printf(\ return 0; }

上面第二类与第三类的代码复杂度都是O（n^3)，n为石子堆数目，那么还有没有复杂度更低的方法呢？有的。也是使用动态规划，由于过程满足平行四边形法则，优化后可以将复杂度降为O（n^2)。