【算法设计与分析】动态规划解决石子合并问题

摘要

动态规划算法是计算机算法设计中的一个重要算法，通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决，石子合并问题作为典型算例，能够彰显动态规划算法特征
针对石子合并问题，本文利用动态规划算法寻求石子合并时的最大,最小得分，选择相邻的两堆石子堆进行合并，其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程，利用程序进行求解。算例结果显示：将4堆石子合并成一堆，每堆的石子个数分别是4,4,5,9，合并的代价最小得分为43，最大得分为54

1、问题描述

在一个圆形操场的四周摆放着N堆石子，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。计算出将n堆石子合并成一堆的代价最大得分和最小得分。

2、问题分析

首先分析本题。题目输入的数据是石子堆的个数n，以及每堆石子堆的数量ai。合并的过程中，只能选择相邻的两堆石子堆进行合并。所以最终花费的代价，与石子堆的排列顺序也有关。
此问题具有重叠子结构。首先肯定是两两相邻的石子堆进行合并。最初我们不知道要从哪里开始合并，则遍历所有的石子堆，进行两两合并。比如序列 {1,2,3,4} ，1号和2号合并：sum[1][2]=3，2号和3号合并：sum[2][3]=5 ，3号和4号合并：sum[3][4]=7 ，这里我们用 sum[i][j] 表示当前合并步骤从 i 合并到 j 花费的代价，用 dp[i][j] 表示从 i 和并到 j 的累计代价，第1步的累计代价等于当前步骤的代价。
接下来再进行3个长度的合并，则只有2种合并方案：1号、2号、3号合并或者是2号、3号、4号合并。在1号、2号、3号合并的过程中，则又有两种方案：{{1,2},3} 还是 {1,{2,3}}。对于前者，当前步骤花费代价 sum[1][3] = sum[1][2] + sum[3][3] = 3+3 = 6 ，加上第一步已经花费的代价 sum[1][2]=3 ，总代价为 dp[1][3] = sum[1][2] + sum[1][3] = 9 ；对于后者，花费代价 sum[1][3] = sum[1][1] + sum[2][3] = 1+5 = 6 ，加上第一步已经花费的代价 sum[2][3]=5 ，总代价为 dp[1][3] = sum[1][3] + sum[2][3] = 9 。所以第二轮的最少代价应该在第一种方案中。
通过上面这个简单的示例，可以归纳总结出，实际的从 i 到 j 的最小合并代价，应该是选择：从已有的 i 到 j 的最小合并代价，与从 i 到 k 的最小代价、从 k+1 到 j 的最小代价、当前步骤从 i 到 j 的合并代价的和的最小值。

即状态转移方程为：

3.算法设计

通过状态转移方程我们可以看出dp[ i ][ t ]表示从 第i堆开始之后合并t堆石子(包括第i堆石子)合并花费，k是i~t之间的一个数，因为是环形,所以要将一维数组收尾相连,所以计算第i+k堆应该表示成: (i+k-1)%n+1,这里不能想当然的以为-1%n可以和外面的1约掉就变成(k+1)%n， 这里是因为数组的下标是从1开始的，前者可以保证不去到0，用sum表示最后两队合并时候的花费，sum一定等于所有石子的个数。

4.程序代码

#include
#include
#define Ma_x 99999
#define Mi_x 0 
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b 

int n,w[200],dp[200][200],dq[200][200];//n表示堆数，w表示每队的数量，dp[i][j]表示从第i堆开始合并j堆（包括第i堆）后的最小花费 ,dq表示最大 

int sum(int i,int t){//从第i堆开始,t个石堆合，最后一次的合并的花费 
    int k,s=0,k1;
    for(k=i;k<i+t;k++){
        k1=k%n;
        if(k1==0) k1=n;
        s=s+w[k1];   //这t个石堆最好两堆合并时的花费一定是这t堆石子的总和 
    }
    return s;
}

int main(){
    int i,t,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
        dp[i][1]=0;//表示合并一堆的花费，没有合并则花费为0 
       
	}
    //动态规划
    for(t=2;t<=n;t++){
        for(i=1;i<=n;i++){
            dp[i][t]=Ma_x;
            dq[i][t]=Mi_x; 
            for(k=1;k<t;k++){
                dp[i][t]=min(dp[i][t],dp[i][k]+dp[(i+k-1)%n+1][t-k]+sum(i,t));
                dq[i][t]=max(dq[i][t],dq[i][k]+dq[(i+k-1)%n+1][t-k]+sum(i,t));
			}
        }
    }
    int mini=Ma_x;
	int maxi=Mi_x; 
    for(i=1;i<=n;i++){//从第几堆石子开始结果最小 
        mini=min(mini,dp[i][n]);  
		maxi=max(maxi,dq[i][n]); 
    }
    printf("%d ",mini); 
    printf("%d ",maxi); 
}

4.运行结果

提供输入数据，第一行是正数n,表示有n堆石子。第二行有n个数，表示每堆石子的个数。
由输出结果可知，将4堆石子合并成一堆，每堆的石子个数分别是4,4,5,9，2、3堆合并的最小得分为43，3、4堆最大得分为54。
1.5.2时间复杂度分析
一维动态规划时间复杂度一般有O(n)和O(n^2)两种，时间复杂度取决于状态转移方程。
如果第i个状态的确定需要利用前i-1个状态，即dp[i]由dp[i-1],dp[i-2],…,dp[0]的取值共同决定，那么此时的时间复杂度为此算法的时间复杂度为O（n2），