一：任意版
有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。
此类问题比较简单，就是哈夫曼编码的变形，用贪心算法即可求得最优解。即每次选两堆最少的，合并成新的一堆，直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。
二：直线版
在一条直线上摆着N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。
如果熟悉矩阵连乘对这类问题肯定非常了解。矩阵连乘每次也是合并相邻两个矩阵（只是计算方式不同）。那么石子合并问题可用矩阵连乘的方法来解决。
那么最优子结构是什么呢？如果有N堆，第一次操作肯定是从n-1个对中选取一对进行合并，第二次从n-2对中选取一对进行合并，以此类推……
设best[i][j]表示i-j合并的最优值, sum[i][j]表示第i堆石子到第j堆石子的总数量，递推公式如下：
#include
#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
#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)。
相关推荐：
loading