动态规划之石子合并二(直线形优化)

题目描述

有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

题目解析:

本次讲解是延续了上一期的博客，上一次我们主要是通过三层循环遍历求得合并代价的最小值，没有考虑时间复杂度，链接为https://blog.****.net/chenpeixing361/article/details/88720927。本次主要探讨的主题是如何对上次所写的代码进行优化，降低时间复杂度。上次的代码我们在函数中写了三层循环，第一层代表区间分割长度，第二层代表区间起始的坐标，第三层循环代表分割的位置，那么我们如何进行优化呢？

我们知道当a, b, c, d(a <= b < c <= d)当有cost[a][c] + cost[b][d] <= cost[a][d] + cost[b][c] 时，我们称其满足四边形不等式，设s[i][j]表示当区间[i, j]取最优决策时所选择的下标，这时可以证明有s[i][j - 1] <= s[i][j] <= s[i + 1][j],这时当按区间dp时，计算区间[i, j]的最优解，只要枚举s[i][j - 1], s[i + 1][j]]即可，由于数组s取值为[1, n]且是单调的，所以枚举的总复杂度为O(n)，最后加上区间枚举的复杂度，总复杂度便可以降为为O(n^2)。有关四边形不等式的解释以及证明详见如下链接：https://baike.baidu.com/item/%E5%9B%9B%E8%BE%B9%E5%BD%A2%E4%B8%8D%E7%AD%89%E5%BC%8F/7556574?fr=aladdin，不清楚的同学可以自行查阅。

参考代码：

import java.util.Scanner;

/**
 * 直线型石子合并优化,时间复杂度降为o(n*n)
 * @author autumn_leaf
 * @Date 2019/03/21
 */
public class CombinStones2 {
	
	/**
	 * 石子堆求和
	 * @param stone 石子数组
	 * @param i 区间开头
	 * @param j	区间结尾
	 * @return 石子堆的和
	 */
	static int dpSum(int[] stone,int i,int j) {
		int sum = 0;
		for(int k=i; k<=j; k++) {
			sum += stone[k];
		}
		return sum;
	}
	
	/**
	 * 四边形不等式进行优化
	 * @param stone 石子堆数组
	 * @return 求得dp数组最小值
	 */
	static int dpOptimination(int[] stone) {
		int n = stone.length;
		//dp数组用于存放最优解
		int[][] dp = new int[n+1][n+1];
		//s数组用来存放每次循环后得到的最优分割位置k
		int[][] s = new int[n+1][n+1];
		//数组初始化
		for(int i=0; i<n; i++) {
			dp[i][i] = 0;
			s[i][i] = i;
		}
		//i逆序,原因是求dp[i][j]时调用dp[i+1][j]的最优决策s[i+1][j]
		//j顺序,原因是求dp[i][j]时调用dp[i][j-1]的最优决策s[i][j-1]
		for(int i=n-1; i>=0; i--) {
			for(int j=i+1; j<n; j++) {
				int temp = Integer.MAX_VALUE;
				int fence = 0;
				//主要是这边进行了优化,每次找出k值,这层循环时间复杂度可以忽略
				for(int k=s[i][j-1]; k<=s[i+1][j]; k++) {
					int sum = dpSum(stone,i,j) + dp[i][k] + dp[k+1][j];
					if(temp > sum) {
						temp = sum;
						fence = k;
					}
				}
				//k循环结束后记得保存优化后的值
				dp[i][j] = temp;
				s[i][j] = fence;
			}
		}
		return dp[0][n-1];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			int[] stone = new int[n];
			for(int i=0; i<n; i++) {
				stone[i] = sc.nextInt();
			}
			System.out.println(dpOptimination(stone));
		}

	}

}

在上述代码中，我们新增了s数组，用来保存最优的分割位置，由四边形不等式我们可以得到s[i][j-1]<=k<=s[i+1][j],由于s[i+1][j]-s[i][j-1]=s[i+1][j]-s[i][j]+s[i][j]-s[i][j-1]远小于n,所以这层循环时间复杂度可以忽略，最终也就可以对我们之前的算法进行优化。

运行截图如下：

动态规划之石子合并二(直线形优化)

好了，本期直线形石子合并优化算法讲解结束，有疑惑的同学可以在下方评论区留言哦！

动态规划之石子合并二(直线形优化)

相关推荐