动态规划之石子合并一(Java 版本)

题目描述

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

输入

有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开。

输出

输出总代价的最小值，占单独的一行。

样例输入

3
1 2 3
7
13 7 8 16 21 4 18

样例输出

9
239

题目解析：

本题是直线型的石子合并，我们可以采用贪心算法，只要每一次都合并两个最小的石子堆，那么最后得到的总代价必然最小。其中，我们需要用一个sum数组保存不同区间石子堆的和，另外设一个dp二维数组,用来记录总代价，我们假设i<j,则dp[i][j]等于[i,j]区间的石子和sum加上[i,j]区间的最优化石子合并解，得到的状态方程如下:

参考代码如下：

import java.util.Arrays;
import java.util.Scanner;

/**
 * 石子合并
 * @author autumn_leaf
 * @Date 2019/03/21
 */
public class CombinStones {

	static int max = 0x3f3f3f3f;
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()) {
			int n = sc.nextInt();
			//石子数组
			int[] num = new int[n+1];
			//石子堆数组
			int[] sum = new int[n+1];
			//记忆化数组,用来记录总的代价
			int[][] dp = new int[n+1][n+1];
			//dp数组初始化
			for(int i=0;i<=n;i++) {
				Arrays.fill(dp[i],max);
			}
			sum[0] = 0;
			//sum数组初始化
			for(int i=1;i<=n;i++) {
				num[i] = sc.nextInt();
				sum[i] = num[i] + sum[i-1];
				dp[i][i] = 0;
			}
			//第一层len代表区间长度
			for(int len=1; len<n; len++) {
				//第二层i代表区间开头
				for(int i=1; i+len<=n; i++) {
					int j = i+len;
					//第三层k代表区间分割的位置
					for(int k=i; k<j; k++) {
						dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
					}
				}
			}
			//即代表1-n石子的最小代价
			System.out.println(dp[1][n]);
		}
	}
	
}

运行截图如下：

好了，接下来我可能会讲解环型石子合并问题了，有疑惑的小伙伴可以在下方评论区留言哦！