本文共 2266 字，大约阅读时间需要 7 分钟。
JAVA算法：合并石子堆——JAVA版本算法（动态规划算法）
在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
请编写算法，读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案，使得做n－1次合并，得分的总和最小。
例如：有4堆石子：4 4 5 9
则最佳合并方案如下：
4 4 5 9 score: 0 8 5 9 score: 8 13 9 score: 8 + 13 = 21 22 score: 8 + 13 + 22 = 43 输入信息可能有多组测试数据。 当输入n=0 时，结束。
第一行为石子堆数 n (1<=n<=100)；第二行为 n 堆的石子每堆的石子数,每两个数之间用一个空格分隔。
输出信息合并的最小得分，每个结果一行。
问题解析这个问题和直线型的区别在于最后一堆和第一堆也是相邻的，可以把圆形转换成直线型，把问题扩展为2n-1堆石子。
例如：如果环形石子堆是 4 4 5 9，那么转换成直线型就变成了 4 4 5 9 4 4 5，所以最终就不是计算 0~n-1了，而是在 0~n-1，1-n，2-n+1，...，n-1~2n-2中选择最小的。
计算方法和直线型的相同。
算法设计
package com.bean.algorithm.beginner;import java.util.Scanner;public class MergeStones { private static int n; private static int[] arr; private static int[] sum; private static int[][] dp; /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); n = sc.nextInt(); arr = new int[2 * n]; sum = new int[2 * n]; for (int i = 1; i <= n; i++) { arr[i] = sc.nextInt(); sum[i] = sum[i - 1] + arr[i]; } for (int i = n + 1; i <= 2 * n - 1; i++) { arr[i] = arr[i - n]; sum[i] = sum[i - 1] + arr[i]; } minFun(); maxFun(); } private static void minFun() { dp = new int[2 * n][2 * n]; for (int r = 1; r <= n - 1; r++) { for (int i = 1; i <= 2 * n - 1; i++) { int j = i + r; if (j >= 2 * n) { continue; } dp[i][j] = dp[i][i] + dp[i + 1][j] + sum[j] - sum[i - 1]; for (int k = i + 1; k < j; k++) { dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]); } } } int result = dp[1][n]; for (int i = 2; i <= n; i++) { result = Math.min(result, dp[i][n - 1 + i]); } System.out.println(result); } private static void maxFun() { dp = new int[2 * n][2 * n]; for (int r = 1; r <= n - 1; r++) { for (int i = 1; i <= 2 * n - 1; i++) { int j = i + r; if (j >= 2 * n) { continue; } dp[i][j] = dp[i][i] + dp[i + 1][j] + sum[j] - sum[i - 1]; for (int k = i + 1; k < j; k++) { dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]); } } } int result = dp[1][n]; for (int i = 2; i <= n; i++) { result = Math.max(result, dp[i][n - 1 + i]); } System.out.println(result); }} 程序运行结果：
输入信息：
4
4 4 5 9输出结果;
43
54
转载地址：http://lntdi.baihongyu.com/