石子合并问题

---

---

石子合并动态规划解决

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
测试用例：
4（石子的堆数）
4 4 5 9（每一堆的石子数目）
输出： 43 54

分析：

首先，注意这是圆形的操场，石子堆圆形摆放，也就是最后一堆石子可以和第一堆石子合并，可以通过不同石子堆分别打头排列，解决这个问题。
　　因为用的方法是动态规划，所以肯定要为数组首先打好底，这样后续操作才能在此基础上进行。
　　此题与矩阵连乘问题相比，先计算每一堆石子自己合并的情况（这就是数组打底），然后一个循环，r控制2堆，3堆，4堆.......n堆石子合并；每i堆石子合并的时候，需要控制起始位置，i代表从哪一堆开始合并，j代表到哪一堆合并结束。
　　这样，i,j就控制了一个范围，在这个范围内分成r堆合并。但究竟r在哪个地方分开，才能获得最优值，我们是不知道的，需要i,j范围都遍历看一看。
　　还有就是递推公式，类比矩阵连乘问题理解，i到k的计算量+k到j的计算量+i到j的石子总数，就是当前m[i][j]的值，代表i堆到j堆合并的最大（最小）得分。

#include<stdio.h>
#define n 4   // 4堆石子 
int stone[n]={4,4,5,9};

int Max(){
    int m[n][n]={0};   //m[i][j]是i堆到j堆合并的最大得分 
    int i,j,k,r,t;
    int sum=0;   //i堆到j堆的石子数 
    //每一堆自己合并
    for(i=0;i<n;i++)
        m[i][i]=0; 
    //两堆以上合并
    for(r=2;r<=n;r++){
        for(i=0;i<=n-r;i++){
            j=i+r-1;
            sum=0;
            for(k=i;k<=j;k++)
                sum+=stone[k];
            m[i][j]=m[i][i]+m[i+1][j]+sum;
            for(k=i+1;k<j;k++){
                t=m[i][k]+m[k+1][j]+sum;
                if(t>m[i][j])
                    m[i][j]=t;
            }        
        }
    }
    return m[0][n-1];
}

int Min(){
    int m[n][n]={0};   //m[i][j]是i堆到j堆合并的最大得分 
    int i,j,k,r,t;
    int sum=0;   //i堆到j堆的石子数 
    //每一堆自己合并
    for(i=0;i<n;i++)
        m[0][0]=0; 
    //两堆以上合并
    for(r=2;r<=n;r++){
        for(i=0;i<=n-r;i++){
            j=i+r-1;
            sum=0;
            for(k=i;k<=j;k++)
                sum+=stone[k];
            m[i][j]=m[i][i]+m[i+1][j]+sum;
            for(k=i+1;k<j;k++){
                t=m[i][k]+m[k+1][j]+sum;
                if(t<m[i][j])
                    m[i][j]=t;
            }        
        }
    }
    return m[0][n-1];
}
int main(){
    int max=0,min=10000;
    int temp=0,tmax,tmin; 
    for(int i=0;i<n;i++){
        temp=stone[0];               //因为是圆形的，不断轮换，每个元素都打头，
        for(int j=0;j<n-1;j++){      //就实现了最后一堆石子和第一堆的合并
            stone[j]=stone[j+1];
        }
        stone[n-1]=temp;
        tmax=Max();
        tmin=Min();
        if(tmax>max)
            max=tmax;
        if(tmin<min)
            min=tmin;
    } 
    printf("最大：%d\n最小：%d\n",max,min);   
    return 0;
} 

运行截图