本文共 3755 字，大约阅读时间需要 12 分钟。

一、题目：

有n堆石子，现在要将它们有次序的合并成一堆，每次只能相邻两队合并成为新的一堆，并且将新的一堆石子数目记为这次合并分数，计算n堆石子合并成一堆的最小的得分和最大得分。（1<=n<=100）

• 情况一：石子依次排成一行
• 情况二：石子依次排成一圈

二、分析：

• 情况一：石子依次排成一行

该问题的求解首先在于如何减少整个问题的求解规模以后如何通过子问题得到整个问题的最优解。

因为从哪一个石子堆开始合并，以及向左还是向右合并，都需要考虑到，所以我们借助二维数组进行全面构建整个过程，又因为求解最大值以及最小值，求解的逻辑不一，所以我们需要两个二维数组进行求解。

在求解的过程中，我们需要控制好问题的规模，使规模由2个直到最大，这样在后续问题规模变大求解时，我们可以利用前期所得的局部最优解，最终逐层推进达到整体最优。

在数组中构建的情形，有点类似于杨辉三角的逻辑，不同在于杨辉三角是自定向下的逐步累加，但是该算法是自底向上的逐步累加，最终在二维数组的右上角获得最终结果。

• 情况二：石子依次排成一圈

该问题可以转换成为上一个问题，关键在于如何“化曲为直”，解决办法就是在原有n个石子堆后面再放n-1与之前n堆前n-1个相同石子堆，这样就可以构建圆型了。

此时整个2n-1长度的石子堆中选取n个连续的石子堆就可以构成圆型的石子堆所有的分配情况。

最后在结果获取的时候，因为逻辑上是一个圆型，因此起点和终点可以是任意的，所以最大值取Max[i][n+i-1]（2<=i<=n）中的最大值，最小值取Max[i][n+i-1]（2<=i<=n）中的最小值。（因为二维数组的下标表示了合并规模的起点和终点。）

总的来说，那后面新加的n-1个有点像“工具人”，使得问题规模从n-1扩大到2*n-1，但是最后每次看的都是n个构建的最优解，再比较不同n个之间的最优解。从而达到整体最优。

三、代码：

• 情况一：石子依次排成一行

求解max递推式类似！ 

import java.util.Scanner;public class demo{	public static void main(String[] args) {		int n;//记录石子的堆数		System.out.println("请输入石子的堆数(1~100):");		Scanner s = new Scanner(System.in);		n = s.nextInt();		if(n>100||n<1) {//越界报错提醒			System.out.println("输入有误！");			System.exit(0);		}				int []count = new int[101];//记录每一堆的石子数目		System.out.println("请依次输入各堆的石子数目：");		for(int i = 1;i<=n;i++)			count[i] = s.nextInt();				straight(count, n);		System.out.println("最大值为："+Min[1][n]+"最小值为："+Max[1][n]);					}	    //二维数组的下标决定了合并的起点和终点	public static int[][] Max = new int[101][101];//记录整个最大值的求解过程	public static int[][] Min = new int[101][101];//记录整个最小值的求解过程	public static int[] sum = new int[101];//便于求解合并之后的石子堆数目的和		public static void straight(int a[],int n) {		//初始化		for(int i=1;i<=n;i++) {			Min[i][i] = 0;			Max[i][i] = 0;		}				sum[0] = 0;//便于后续求石子的数量和，直接减一下就好了		for(int i = 1;i<=n;i++)			sum[i] = sum[i-1]+a[i];				//在这里利用变量v控制问题的规模，使得求解过程中先利用求解小问题的局部最优解		//在后续求解规模逐渐增大时，可以使用到前面已知的局部最优解，进而最后达到整体最优		for(int v = 2;v<=n;v++) {//控制合并石子堆的数目			for(int i = 1;i<=n-v+1;i++) {//控制合并起点				int j = i+v-1;//控制合并终点				Min[i][j] = 1000;				Max[i][j] = -1;				int tmp = sum[j]-sum[i-1];//求之间石子之和				for(int k = i;k
   
    (Max[i][k]+Max[k+1][j]+tmp)?Max[i][j]:(Max[i][k]+Max[k+1][j]+tmp);				}							}		}	}}//运行结果：/*请输入石子的堆数(1~100):4请依次输入各堆的石子数目：4 4 5 9最大值为：43最小值为：54*/
   

• 情况二：石子依次排成一圈

import java.util.Scanner;public class demo{	public static void main(String[] args) {		int n;//记录石子的堆数		System.out.println("请输入石子的堆数(1~100):");		Scanner s = new Scanner(System.in);		n = s.nextInt();		if(n>100||n<1) {//越界报错提醒			System.out.println("输入有误！");			System.exit(0);		}				int []count = new int[101];//记录每一堆的石子数目		System.out.println("请依次输入各堆的石子数目：");		for(int i = 1;i<=n;i++)			count[i] = s.nextInt();		//不同之处		for(int i=n+1;i<=2*n-1;i++)			count[i]=count[i-n];				straight(count, 2*n-1);				int min = Min[1][n];//初始化		int max = Max[1][n];				for (int i = 2;i<=n;i++) {//获取结果			if(Min[i][n+i-1]
   
    max)				max = Max[i][n+i-1];		}		//不同之处		System.out.println("最大值为："+min+"最小值为："+max);					}		//二维数组的下标决定了合并的起点和终点	public static int[][] Max = new int[101][101];//记录整个最大值的求解过程	public static int[][] Min = new int[101][101];//记录整个最小值的求解过程	public static int[] sum = new int[101];//便于求解合并之后的石子堆数目的和		public static void straight(int a[],int n) {		//初始化		for(int i=1;i<=n;i++) {			Min[i][i] = 0;			Max[i][i] = 0;		}				sum[0] = 0;//便于后续求石子的数量和，直接减一下就好了		for(int i = 1;i<=n;i++)			sum[i] = sum[i-1]+a[i];				//在这里利用变量v控制问题的规模，使得求解过程中先利用求解小问题的局部最优解		//在后续求解规模逐渐增大时，可以使用到前面已知的局部最优解，进而最后达到整体最优		for(int v = 2;v<=n;v++) {//控制合并石子堆的数目			for(int i = 1;i<=n-v+1;i++) {//控制合并起点				int j = i+v-1;//控制合并终点				Min[i][j] = 1000;				Max[i][j] = -1;				int tmp = sum[j]-sum[i-1];//求之间石子之和				for(int k = i;k
    
     (Max[i][k]+Max[k+1][j]+tmp)?Max[i][j]:(Max[i][k]+Max[k+1][j]+tmp);				}							}		}	}}//求解结果/*请输入石子的堆数(1~100):6请依次输入各堆的石子数目：5 8 6 9 2 3最大值为：81最小值为：130*/
    
   

Ending... ...

转载地址：http://mlmg.baihongyu.com/