石头合并/动态规划_生旦净末灰

题目描述

矩阵连乘

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

如，[1,3,5,2]，合并三次：1+3=4，5+2=7，4+7=11，总代价：4+7+11=22.

思路：
动态规划，遍历合并区间长度，每次合并两个较小的堆，dp二维数组表示区间i_{j的最小代价，dp[i][j]等于[i,j]区间的石子和sum，加上[i,j]区间的最优化石子合并解，即区间i}j在k处分割成两堆之和。

package Java;

public class Test {


	public static void stone(int[] nums) {
		if (nums.length == 1) {
			System.out.println(nums[0]);
			return;
		}
		int l = nums.length;
		// 动态规划 dp[i][j]：区间i~j之间
		int[][] dp = new int[l + 1][l + 1];
		// 前缀和



		
		// 最外层区间长度
		for (int len = 2; len <= nums.length; len++) {
			// 区间i~j，平移计算每个区间
			for (int i = 1, j = len; j <= nums.length; i++, j++) {
				int min = Integer.MAX_VALUE;
				// k：分割位置
				for (int k = i; k < j; k++) {
					// 可以用前缀和
					if (min > dp[i][k] + dp[k + 1][j] + getSum(nums, i - 1, j - 1))
						min = dp[i][k] + dp[k + 1][j] + getSum(nums, i - 1, j - 1);
				}
				dp[i][j] = min;
			}
		}
		System.out.println(dp[1][nums.length]);
		return;
	}

	
	public static int getSum(int[] nums, int left, int right) {
		int sum = 0;
		for (int i = left; i <= right; i++)
			sum += nums[i];
		return sum;
	}

	public static void main(String[] args) {
		int[] num = { 1, 3, 5, 2 };
		stone(num);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49