详解动态规划石子合并问题(直线型, 环形)

朴灿烈づ我的快乐病毒、 2022-02-22 21:14 215阅读 0赞

### 题目描述 ###

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，合并的花费为这相邻两堆之和

试设计出1个算法,计算出将N堆石子合并成1堆的最小花费和最大花费.

输入输出格式

输入格式：  
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输入示例  
4  
4 4 5 9  
输出示例  
43  
54

### 算法分析 ###

动态规划

*  dp\[i\]\[t\]=min(dp\[i\]\[t\],dp\[i\]\[k\]+dp\[(i+k-1)%n+1\]\[t-k\]+sum(i,t))
 *  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表示最后两队合并时候的花费,一定等于所有石子的个数.

\-则求dp\[ i \]\[ n \]的最小解，1<=i<=n;

可以把dp\[ i \]\[ n \]看成一堆，这一堆的最优解是由 由这堆分割的两小堆合并的。 然后每两小堆又可以再分,知道分成两堆的石子合并,前面这部分是分治法的思想, 但是值得注意的是选择不同的堆作为第一堆,得到的结果不一样,这样如果每个每种情况都像这样分,就会有很多重复的,以致时间复杂度达到指数级, 所以我们要想办法吧子问题的结果保留下来, 然后再得到最优解.这就是动态规划的思想. 最普遍的做法是自底向上将子问题的保存在数组中.

### 代码 ###

#include<stdio.h>
    #include<string.h>
    #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 
            dq[i][1]=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); 
    }

### 直线型合并 ###

直线型合并的和环形合并,区别有两点:

*  不用将数组连起来
 *  最后的结果只有一种情况就是dp\[i\]\[n\]

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #define min(a,b) a<b?a:b
    int a[50005];
    int dp[505][505];
    int sum[505];
    
    
    int main()
    { 
        int n;
       scanf("%d",&n);
    
            for(int i=1; i<=n; i++)
            { 
                scanf("%d",&a[i]);
                dp[i][i]=0;
                sum[i]+=a[i]+sum[i-1];
            }
    
            for(int l=1; l<=n-1; l++)//l是合并的次数
    
            { 
                for(int i=1; i<=n-l; i++)//i是在当前合并次数下区间的首地址
                { 
                    int j=i+l;
                     dp[i][j]=9999;
                    for(int k=1; k<=j-1; k++)//j是相应的末地址
    
                    { 
                        dp[i][j]=min(dp[i][j],(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]));
                       
                    }
                }
            }
            printf("%d\n",dp[1][n]);
    
        return 0;
    }