四边形不等式技巧（上）

文章目录

  • 1、引入
    • 1.1 题目描述
    • 1.2 思路分析
    • 1.3 代码实现
    • 1.4 小结
  • 2、题目二
    • 2.1 题目描述
    • 2.2 思路分析
    • 2.3 代码实现
    • 2.4 小结
  • 3、题目三：合并石子
    • 3.1 题目描述
    • 3.2 思路分析
    • 3.3 代码实现
    • 3.4 枚举优化
    • 3.5 对数器
  • 4、四边形不等式技巧特征
  • 5、应用：画家问题
    • 5.1 题目描述
    • 5.2 思路分析
    • 5.3 代码实现
  • 6、四边形不等式技巧注意点

本文讲解区间划分问题中的划分点不回退现象。

1、引入

1.1 题目描述

给定一个非负数组arr，长度为 N N N，那么有 N − 1 N-1 N−1 种方案可以把 arr 切成左右两部分。

每一种方案都有， m i n min min{左部分累加和，右部分累加和}

求这么多种方案中， m i n min min{左部分累加和，右部分累加和} 的最大值是多少？

整个过程要求时间复杂度 O ( N ) O(N) O(N)。

1.2 思路分析

最优解思路：首先求出全局累加和，然后左部分不断地扩，扩的过程中记录左右部分累加和的最大值。

1.3 代码实现

public class BestSplitForAll {
	
	//暴力解
	public static int bestSplit1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int ans = 0;
		for (int s = 0; s < N - 1; s++) {
			int sumL = 0;
			for (int L = 0; L <= s; L++) {
				sumL += arr[L];
			}
			int sumR = 0;
			for (int R = s + 1; R < N; R++) {
				sumR += arr[R];
			}
			ans = Math.max(ans, Math.min(sumL, sumR));
		}
		return ans;
	}
	
	//最优解
	public static int bestSplit2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int sumAll = 0;
		//遍历数组记录全局累加和
		for (int num : arr) {
			sumAll += num;
		}
		int ans = 0;
		int sumL = 0; //划分的左部分的累加和
		// [0...s]  [s+1...N-1]
		for (int s = 0; s < N - 1; s++) {
			sumL += arr[s];
			int sumR = sumAll - sumL;
			ans = Math.max(ans, Math.min(sumL, sumR));
		}
		return ans;
	}

	public static int[] randomArray(int len, int max) {
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = (int) (Math.random() * max);
		}
		return ans;
	}

	public static void main(String[] args) {
		int N = 20;
		int max = 30;
		int testTime = 1000000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * N);
			int[] arr = randomArray(len, max);
			int ans1 = bestSplit1(arr);
			int ans2 = bestSplit2(arr);
			if (ans1 != ans2) {
				System.out.println(ans1);
				System.out.println(ans2);
				System.out.println("Oops!");
			}
		}
		System.out.println("测试结束");
	}
}

1.4 小结

本题是在 [ 0 , N − 1 ] [0, N-1] [0,N−1] 范围上的最优划分问题，最后只需要返回一个值，即是这个范围上最优划分所得累加和的最大值。

接下来，问题升级，要返回一个数组， i i i 位置的值表示在 [ 0 , i ] [0,i] [0,i] 范围上最优划分的结果。

2、题目二

2.1 题目描述

把引入题目中提到的， m i n min min{左部分累加和，右部分累加和}，定义为 S(N-1)，也就是说：

S(N-1)：在 arr[0...N-1] 范围上，做最优化分所得到的的 m i n min min{左部分累加和，右部分累加和} 的最大值。

现在要求返回一个长度为 N N N 的 s s s 数组， s [ i ] s[i] s[i] 为在 arr[0...i] 范围上做最优化分所得到的 m i n min min{左部分累加和，右部分累加和} 的最大值。

得到整个 s s s 数组的过程，要求时间复杂度为 O ( N ) O(N) O(N)。

2.2 思路分析

如果使用暴力解，对于每一个 [ 0 , i ] [0,i] [0,i] 范围都尝试每种划分方案，那么时间复杂度 O ( N 2 ) O(N^2) O(N2)。

假设对于范围 [0, 17] 已经知道最优划分是 [0,8] 和 [9,17]，即在8和9中间分开，接下来要看的是 [0,18] 范围，如果可以证明[0,17]的划分线不需要回退**，则可以简化 [0,18] 这个范围上最优划分的尝试过程。

如果 [0,17] 的划分线不需要回退，那么表示 [0,18] 这个范围的划分方案可以从[0,8]、[9,18] 开始尝试，而之前的那些方案如[0,0]、[1,18]… 都可以舍弃。

注意：对于某个范围上的最优划分，划分点本身就是不会回退的，确定划分点的位置就是当前能得到的答案不小于划分点往右移得到的答案。也就是说，如果划分点右移会使得答案变小，那就不再往右移。

也就是说，对于上面提到的例子，当[0,17]的最优划分为[0,8]、[9,17]的时候，考虑[0,18]的最优划分时就直接将8和9这个划分点往右移动，直到如果继续往右移动会使得答案变小停止，就找到了[0,18]范围的划分点；而考虑[0,19]范围的最优划分时，直接从[0,18]的划分点开始往右移动进行尝试。这个过程就是 O ( N ) O(N) O(N)，因为划分点是不会往回退的。

证明：[0,i] 范围的最优划分点在 [0,i+1] 范围上一定不回退。

首先整个数组是非负的。

其次，假设 [0,17] 范围上划分点在 8 和 9 之间，接下来考虑[0,18]范围的划分点。则分为如下情况：

  1. [0,17] 范围上的最优划分的答案来自左部分，即「左部分的值 < 右部分的值」，而新来的18位置的数自然地会被划分到右部分，在已经知道 [0,17] 范围上的答案瓶颈的情况下（即8和9之间划分是能得到最佳答案的最终位置），那么这个划分点就不会再往左移动，因为那样，左部分的值会更小，则答案也会更小。
  2. [0,17] 范围上的最优划分的答案来自右部分，即「左部分的值 > 右部分的值」，则 18 位置的数自然地会被划分到右部分，此时分几种情况：
    • 如果 18 位置的数进来后，右部分的值不再是瓶颈，即 「左部分的值 < 新右部分的值」，左部分变成了瓶颈，如果划分点往左移，那么左部分就会变得更小，答案就更小了；
    • 如果 18 位置的数进来后，右部分的值依然是瓶颈，即 「左部分的值 > 新右部分的值」，划分点依然不能往左移，因为如果可以往左移，当初在范围[0,17]的最优划分点寻找的时候就往左了。当初的划分点就已经找到了最佳瓶颈值，如果往左移，只会使得瓶颈值变小，现在新加入了数之后右部分依然是瓶颈值，且值还增大了，那就更不能往左移动了。如 [3, 100, 8, 9, 10]，对于[0,4]范围的最佳划分点为100和8之间，答案为17，当10进来后，最佳划分点依然是100和8之间，答案为27。[0,4]范围上在100和8之间划分，此时右侧是瓶颈，如果划分点往左移了，则左侧成了瓶颈，且这个瓶颈的值还不如100和8之间划分得到的右部分这个瓶颈值。

至此，证明了 [ 0 , i ] [0,i] [0,i] 范围上的划分点一旦确定，则 [ 0 , i + 1 ] [0, i+1] [0,i+1] 范围上直接从 [0,i] 范围的划分点开始尝试， i + 2 i+2 i+2 位置接着 [ 0 , i + 1 ] [0,i+1] [0,i+1] 的划分点往下尝试，这个划分点永远不会回退。

这并不是严格的数学证明，只是讲了个道理。这也是本文的精髓所在——不证明。

那么如何验证正确性呢？使用对数器。

2.3 代码实现

public class BestSplitForEveryPosition {
	
	//暴力解 O(N^3）
	public static int[] bestSplit1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return new int[0];
		}
		int N = arr.length;
		int[] ans = new int[N];
		ans[0] = 0;
		for (int range = 1; range < N; range++) {
			for (int s = 0; s < range; s++) {
				int sumL = 0;
				for (int L = 0; L <= s; L++) {
					sumL += arr[L];
				}
				int sumR = 0;
				for (int R = s + 1; R <= range; R++) {
					sumR += arr[R];
				}
				ans[range] = Math.max(ans[range], Math.min(sumL, sumR));
			}
		}
		return ans;
	}

	// 求原来的数组arr中，arr[L...R]的累加和
	public static int sum(int[] sum, int L, int R) {
		return sum[R + 1] - sum[L];
	}
	
	//简单优化：使用了前缀和数组, O(N^2)
	public static int[] bestSplit2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return new int[0];
		}
		int N = arr.length;
		int[] ans = new int[N];
		ans[0] = 0;
		int[] sum = new int[N + 1];
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + arr[i];
		}
		for (int range = 1; range < N; range++) {
			for (int s = 0; s < range; s++) {
				int sumL = sum(sum, 0, s);
				int sumR = sum(sum, s + 1, range);
				ans[range] = Math.max(ans[range], Math.min(sumL, sumR));
			}
		}
		return ans;
	}
	
	//最优解：O(N), 划分点不回退
	public static int[] bestSplit3(int[] arr) {
		if (arr == null || arr.length == 0) {
			return new int[0];
		}
		int N = arr.length;
		int[] ans = new int[N];
		ans[0] = 0; //[0,0]范围划分，答案为0，即要么左侧没数，要么右侧没数
		// arr =   {5, 3, 1, 3}
		//          0  1  2  3
		// sum ={0, 5, 8, 9, 12} 多一个位置是为了方便计算范围上的累加和，在sum函数中使用
		//       0  1  2  3   4
		// 0~2 ->  sum[3] - sum[0]
		// 1~3 ->  sum[4] - sum[1]
		int[] sum = new int[N + 1]; //前缀和数组，多补个位置，是常见的技巧，避免判断边界
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + arr[i];
		}
		
		//best是不回退的
		int best = 0; // 最优划分，0~range-1上，最优划分是左部分[0~best]  右部分[best+1~range-1]
		for (int range = 1; range < N; range++) { //求[0, range]范围上的最优划分
			while (best + 1 < range) { //划分点是否能继续往右移动。如[0,6]范围上，在4位置划分了，即此时best=4，[0,4][5,6]，则划分点可以继续右移划分为[0,5] [6,6]
				int before = Math.min(sum(sum, 0, best), sum(sum, best + 1, range)); //当前划分点，左部分[0,best]范围，右部分[best+1, range)范围
				int after = Math.min(sum(sum, 0, best + 1), sum(sum, best + 2, range)); //如果划分点右移，左[0,best+1]，右[best+2, range)
				// 注意，一定要是>=，只是>会出错，因为数组中含0，没法继续往下划分
				// 如 [5, 0, 0, 5, 5, 5]
			 	// 	   0  1  2  3  4  5
				if (after >= before) { //划分点右移得到的结果 >= 划分点不右移得到的结果，则划分点右移
					best++;
				} else {
					break;
				}
			}
			ans[range] = Math.min(sum(sum, 0, best), sum(sum, best + 1, range));
		}
		return ans;
	}

	public static int[] randomArray(int len, int max) {
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = (int) (Math.random() * max);
		}
		return ans;
	}

	public static boolean isSameArray(int[] arr1, int[] arr2) {
		if (arr1.length != arr2.length) {
			return false;
		}
		int N = arr1.length;
		for (int i = 0; i < N; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		int N = 20;
		int max = 30;
		int testTime = 1000000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * N);
			int[] arr = randomArray(len, max);
			int[] ans1 = bestSplit1(arr);
			int[] ans2 = bestSplit2(arr);
			int[] ans3 = bestSplit3(arr);
			if (!isSameArray(ans1, ans2) || !isSameArray(ans1, ans3)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("测试结束");
	}
}

2.4 小结

本题每个位置上的答案:
a n s = m a x { m i n { 左部分累加和，右部分累加和 } } ans = max\{ min\{左部分累加和，右部分累加和\}\} ans=max{min{左部分累加和，右部分累加和}}
存在不回退。

再抽象化，一个通式：
a n s = 最优 { 最差 { 左某指标，右某指标 } } ans = 最优\{最差\{左某指标，右某指标\}\} ans=最优{最差{左某指标，右某指标}}
本题中的「某指标」就是「累加和」，「最差」对应「某种划分的最小值」，「最优」对应「所有划分中这个指标最差中的最优」。

如果其他题目也存在着这样的一种关系，可能都存在不回退现象。

同样地，
a n s = 最差 { 最优 { 左某指标，右某指标 } } ans = 最差\{最优\{左某指标，右某指标\}\} ans=最差{最优{左某指标，右某指标}}

如果本题求的是划分后左右部分累加和最大的最小值，那依然是存在不回退的。

关键点在于 「指标」和「区间」之间存在「单调性」，如非负数组的累加和随着区间变大不会变小，如果又是类似上述的范式，可能都存在不回退现象。

不需要证明，而是使用对数器验证。

3、题目三：合并石子

3.1 题目描述

摆放着 n n n 堆石子。

现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

求出将 n n n 堆石子合并成一堆的最小得分（或最大得分）合并方案。

3.2 思路分析

如石子[1, 4, 2, 3]：
第一种合并方法： [1, (4, 2), 3] -> [1, 6, 3] -> [1, (6, 3)] -> [1, 9] -> [(1, 9)] -> [10]，所以总的得分为 6 + 9 + 10 = 25；
第二种合并方法：[(1,4),(2,3)] -> [5, 5] -> [(5,5)] -> [10]，所以总的得分为 5 + 5 + 10 = 20。

和切金条的区别就是必须相邻的才能合并，如果可以移动数字任意合并，那就是贪心问题。

arr 数组的 L 到 R 范围怎么合并才最优？枚举最后一次合并。

arr 数组的 L 到 R 范围上的合并，是一个范围上的尝试，范围动态规划模型。

定义dp[L][R] 表示 L 到 R 范围上最优合并方案下的最小代价。

在这里插入图片描述

3.3 代码实现

// 四边形不等式：合并石子问题
public class StoneMerge {

	public static int[] sum(int[] arr) {
		int N = arr.length;
		int[] s = new int[N + 1];
		s[0] = 0;
		for (int i = 0; i < N; i++) {
			s[i + 1] = s[i] + arr[i];
		}
		return s;
	}

	public static int w(int[] s, int l, int r) {
		return s[r + 1] - s[l];
	}
	
	//暴力递归
	public static int min1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int[] s = sum(arr);
		return process1(0, N - 1, s);
	}

	public static int process1(int L, int R, int[] s) {
		if (L == R) {
			return 0;
		}
		int next = Integer.MAX_VALUE;
		for (int leftEnd = L; leftEnd < R; leftEnd++) {
			next = Math.min(next, process1(L, leftEnd, s) + process1(leftEnd + 1, R, s));
		}
		return next + w(s, L, R);
	}
	
	//动态规划：对枚举没有做任何优化，时间复杂度 O(N^3）
	public static int min2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int[] s = sum(arr); //前缀和数组，加速
		int[][] dp = new int[N][N]; //dp表
		// dp[i][i] = 0
		//对角线都为0，dp表的左下部分都不合法，因为L>R，所以从L = N-2行开始往上填，而列从R = L + 1开始往右
		//两个for循环就是在填所有格子
		for (int L = N - 2; L >= 0; L--) { 
			for (int R = L + 1; R < N; R++) {
				int next = Integer.MAX_VALUE;
				//就是在尝试：[L,leftEnd]作为左部分，[leftEnd+1, R]作为右部分
				// dp(L..leftEnd) + dp[leftEnd+1...R] + 累加和[L...R]
				for (int leftEnd = L; leftEnd < R; leftEnd++) { //枚举所有可能性，没有做任何优化
					next = Math.min(next, dp[L][leftEnd] + dp[leftEnd + 1][R]);
				}
				dp[L][R] = next + w(s, L, R);
			}
		}
		return dp[0][N - 1];
	}
}

3.4 枚举优化

假设要对 dp[3][17] 进行求解，因为 dp 表中是从左往右、从下往上求解的，所以dp[3][17] 的「左侧dp[3][16] 」和 「下方 dp[4][17] 」都是已经求得的。

假设 [3,16] 的最佳划分点为8和9之间，[4,17]的最佳划分点为12和13之间，如果能证明在左侧不用越过8以左，右侧不用越过13以右，那么只需要在 [8,13] 范围内进行尝试即可，而原先对于 dp[3][17] 的求解是要枚举[3,17]范围的所有可能性，现在只需要枚举[8,13]的可能性，所以枚举行为大大改进。也就是对于要求解的位置，如果左方和下方能给出尝试的下限和上限，将大大改进枚举行为。

代码实现：

public class StoneMerge {
	//动态规划，优化枚举行为，时间复杂度 O(N^2)
	public static int min3(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int N = arr.length;
		int[] s = sum(arr);
		int[][] dp = new int[N][N];//dp[L][R]为arr[L...R]最优划分得到的最小代价
		int[][] best = new int[N][N]; //记录得到dp[L][R]的最优划分点
		//dp[i][i] = 0，不存在划分，此时的best[i][i] 不存在，所以对角线跳过
		//倒数第2条对角线，即L=R-1，就是两个相邻的数的合并，dp值为两个数的累加和，best值就是L
		for (int i = 0; i < N - 1; i++) { //for循环就是在填倒数第二条对角线
			best[i][i + 1] = i;
			dp[i][i + 1] = w(s, i, i + 1);
		}
		
		//剩下空格的填充逻辑
		for (int L = N - 3; L >= 0; L--) {//从N-3行开始往上填
			for (int R = L + 2; R < N; R++) { //R=L是对角线，无须填；R=L+1是倒数2条对角线，已经填完，所以从R=L+2开始往右填
				int next = Integer.MAX_VALUE;
				int choose = -1;
				//尝试，下限为[L,R-1]的最优划分点，上限为[L+1,R]的最优划分点，仅在该范围进行尝试
				for (int leftEnd = best[L][R - 1]; leftEnd <= best[L + 1][R]; leftEnd++) {
					int cur = dp[L][leftEnd] + dp[leftEnd + 1][R];
					if (cur <= next) {
						next = cur; //记录最小值
						choose = leftEnd; //记录划分点
					}
				}
				//同时填best和dp值，以便后续的过程的依赖
				best[L][R] = choose;
				dp[L][R] = next + w(s, L, R);
			}
		}
		return dp[0][N - 1];
	}
}

3.5 对数器

public class StoneMerge {
	public static int[] randomArray(int len, int maxValue) {
		int[] arr = new int[len];
		for (int i = 0; i < len; i++) {
			arr[i] = (int) (Math.random() * maxValue);
		}
		return arr;
	}

	public static void main(String[] args) {
		int N = 15;
		int maxValue = 100;
		int testTime = 1000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * N);
			int[] arr = randomArray(len, maxValue);
			int ans1 = min1(arr);
			int ans2 = min2(arr);
			int ans3 = min3(arr);
			if (ans1 != ans2 || ans1 != ans3) {
				System.out.println("Oops!");
			}
		}
		System.out.println("测试结束");
	}
}

4、四边形不等式技巧特征

  1. 两个可变参数的区间划分问题

说明：上述题目很明显都是区间划分问题，可变参数就是区间的范围 L 和 R

  1. 每个格子有枚举行为

说明：如"合并石子"问题中的 dp[i][j] 格子，本来是需要枚举 [i,j] 范围的

  1. 当两个可变参数固定一个，另一个参数和答案之间存在单调性关系

说明：如 “合并石子” 问题中，固定 R，则[L-1,R]范围合并代价 > [L，R]范围合并代价 > [L+1，R]范围合并代价

  1. 而且两组单调关系是反向的：(升 升，降 降) (升 降，降 升)

说明："合并石子"问题中

  • 如果固定R，则L↑，合并代价↓；L↓，合并代价↑；
  • 如果固定L，则R↑，合并代价↑；R↓，合并代价↓。

呈现一种反向的单调关系。

  1. 枚举加速的位置对：「上+右」或者「左+下」

说明："合并石子"问题中，求解某个格子的时候，下限来自左侧，上限来自下侧，则左侧和下侧构成位置对。

如果是上+右，通常是上侧提供下限，右侧提供上限。

只有这两种情况的组合。

存在上述五个特征的，就可以使用四边形不等式技巧，不需要证明，直接用对数器验证！

5、应用：画家问题

5.1 题目描述

给定一个整型数组 arr，数组中的每个值都为正数，表示完成一幅画作需要的时间。

再给定一个整数 num，表示画匠的数量，每个画匠只能画连在一起的画作。

所有的画家并行工作，请返回完成所有的画作需要的最少时间。

例1：

arr=[3,1,4]，num=2。
最好的分配方式为：
第一个画匠画 3 和 1，所需时间为 4。
第二个画匠画 4，所需时间为 4。 
因为并行工作，所以最少时间为 4。
如果分配方式为第一个画匠画 3，所需时间为 3。
第二个画匠画 1 和 4，所需的时间为 5。
那么最少时间为 5，显然没有第一 种分配方式好。

所以返回 4。

例2：

arr=[1,1,1,4,3]，num=3。
最好的分配方式为：
第一个画匠画前三个 1，所需时间为 3。
第二个画匠画 4，所需时间 为 4。 
第三个画匠画 3，所需时间为 3。
返回 4。

可用 [Leetcode]410. 分割数组的最大值 验证。

5.2 思路分析

本题实质就是在求所有画家的画画时间的最大值最小，即 m i n { m a x { 画画时间 } } min\{max\{画画时间\}\} min{max{画画时间}}。

前文的题目中只需要划分成 2 份，而本题需要划分成 num 份。

定义 dp[i][j] 表示 arr数组的 [0, i] 范围上的画必须由 j j j 个画家进行分解，画完的最短时间，不是范围尝试，而是从左往右的尝试，只是多个了画家的参数而已。

如何枚举呢？最后一个画家负责哪个范围的画作进行枚举。

例如 dp[10][3]该如何计算呢？假设 num = 3。

  • 情况1：arr[0...10] 全部由 2 个画家负责，即 dp[10][2]；
  • 情况2：arr[0...9] 由2个画家负责，arr[10] 最后1个画家；
  • 情况3：arr[0...8] 由2个画家负责，arr[9...10] 最后1个画家；
  • …

可见，是通过枚举最后一个画家负责的范围来将整个范围分成左右两部分。
在这里插入图片描述
第0行和第1列可以根据本题本身能很快确定的。☆位置是依赖于其左边一列的。

看看是否符合四边形不等式技巧特征：

  1. 是区间划分问题
  2. 每个格子存在枚举行为
  3. 反向单调关系：
    • 画作数量固定，画家数量↑，则花费时间↓；画家数量↓，花费时间↑；
    • 画家数量固定，画作范围↑，则花费时间↑；画作范围↓，花费时间↓。
  4. 位置对。则从左往右求解，从下往上求解，就会存在「左 + 下」的位置对组合。dp[5][2]这个位置仅仅依赖于前一列，所以直接枚举所有它的依赖项进行计算，最后一行的格子都要使用枚举的方式；而 dp[4][2]位置此时就已经有左和下位置，左侧提供下限，下侧提供上限，以供枚举加速。
  5. 对数器验证！

5.3 代码实现

// leetcode原题
// 测试链接：https://leetcode.com/problems/split-array-largest-sum/
public class SplitArrayLargestSum {

	// 求原数组arr[L...R]的累加和
	public static int sum(int[] sum, int L, int R) {
		return sum[R + 1] - sum[L];
	}

	// 不优化枚举的动态规划方法，O(N^2 * K)
	// 整个表的规模是N*K，而每个格子依赖于前一列，就是对 N 进行枚举，所以复杂度为 O(N^2 * K)
	public static int splitArray1(int[] nums, int K) {
		int N = nums.length;
		int[] sum = new int[N + 1];
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + nums[i];
		}
		int[][] dp = new int[N][K + 1];
		for (int j = 1; j <= K; j++) {
			dp[0][j] = nums[0];
		}
		for (int i = 1; i < N; i++) {
			dp[i][1] = sum(sum, 0, i);
		}
		// 每一行从上往下
		// 每一列从左往右
		// 根本不去凑优化位置对儿！
		for (int i = 1; i < N; i++) {
			for (int j = 2; j <= K; j++) {
				int ans = Integer.MAX_VALUE;
				// 枚举是完全不优化的！
				for (int leftEnd = 0; leftEnd <= i; leftEnd++) { //dp[i][j]位置依赖于前一列的0~i行
					int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1];
					int rightCost = leftEnd == i ? 0 : sum(sum, leftEnd + 1, i);
					int cur = Math.max(leftCost, rightCost);
					if (cur < ans) {
						ans = cur;
					}
				}
				dp[i][j] = ans;
			}
		}
		return dp[N - 1][K];
	}

	// 四边形不等式的解法，用了枚举优化，O(N * K)
	public static int splitArray2(int[] nums, int K) {
		int N = nums.length;
		int[] sum = new int[N + 1];
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + nums[i];
		}
		int[][] dp = new int[N][K + 1];
		//记录最优划分位置，如果best[i][j]=x，则[x,i]是最后一个画家画，而[0,x-1]是前j-1个画家画
		int[][] best = new int[N][K + 1]; 
		
		for (int j = 1; j <= K; j++) { //填第0行
			dp[0][j] = nums[0]; //只有一幅画时，无论多少个画家，耗时都是nums[0]
			best[0][j] = -1; //只有一幅画时，划分点位置为-1，就是在0之前进行划分
		}
		for (int i = 1; i < N; i++) { //填第1列
			dp[i][1] = sum(sum, 0, i); //只有1个画家就是所有画作的累加和
			best[i][1] = -1; //只有1个画家，则该画家负责所有画作，则也是在0之前进行划分
		}
		// 从第2列开始，从左往右
		// 每一列，从下往上
		// 为什么这样的顺序？因为要去凑（左，下）优化位置对儿！
		for (int j = 2; j <= K; j++) {
			for (int i = N - 1; i >= 1; i--) { //i>=1因为第0行已经填过
				int down = best[i][j - 1]; //下限，由左侧提供
				// 如果i==N-1，则不优化上限，就是每一列的最后一个格子，没有下侧位置
				int up = i == N - 1 ? N - 1 : best[i + 1][j]; //上限，由下侧提供
				int ans = Integer.MAX_VALUE;
				int bestChoose = -1;
				for (int leftEnd = down; leftEnd <= up; leftEnd++) { //枚举优化
					//0~leftEnd范围的画由前j-1个画家处理
					int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1]; 
					//leftEnd+1 ~ i范围的画由最后1个画家处理，即求累加和
					int rightCost = leftEnd == i ? 0 : sum(sum, leftEnd + 1, i); 
					int cur = Math.max(leftCost, rightCost);
					// 注意下面的if一定是 <
					// 也就是说，只有取得明显的好处才移动！
					// 举个例子来说明，比如[2,6,4,4]，3个画匠时候，如下两种方案都是最优:
					// (2,6) (4) 两个画匠负责 | (4) 最后一个画匠负责
					// (2,6) (4,4)两个画匠负责 | 最后一个画匠什么也不负责
					// 第一种方案划分为，[0~2] [3~3]
					// 第二种方案划分为，[0~3] [无]
					// 两种方案的答案都是8，但是划分点位置一定不要移动!
					// 只有明显取得好处时(<)，划分点位置才移动!
					// 也就是说后面的方案如果==前面的最优，不要移动！只有优于前面的最优，才移动
					// 比如上面的两个方案，如果你移动到了方案二，你会得到:
					// [2,6,4,4] 三个画匠时，最优为[0~3](前两个画家) [无](最后一个画家)，
					// 最优划分点为3位置(best[3][3])
					// 那么当4个画匠时，也就是求解dp[3][4]时
					// 因为best[3][3] = 3，这个值提供了dp[3][4]的下限
					// 而事实上dp[3][4]的最优划分为:
					// [0~2]（三个画家处理） [3~3] (一个画家处理)，此时最优解为6
					// 所以，你就得不到dp[3][4]的最优解了，因为划分点已经越过2了
					// 提供了对数器验证，你可以改成<=，对数器和leetcode都过不了
					// 这里是<，对数器和leetcode都能通过
					// 这里面会让同学们感到困惑的点：
					// 为啥==的时候，不移动，只有<的时候，才移动呢？例子懂了，但是道理何在？
					// 哈哈哈哈哈，看了邮局选址问题，你更懵！
					if (cur < ans) {
						ans = cur;
						bestChoose = leftEnd;
					}
				}
				dp[i][j] = ans;
				best[i][j] = bestChoose;
			}
		}
		return dp[N - 1][K];
	}
	
	//最优解 O(N*log(sum))  -->sum比较小的时候，这种方式就是最优解；但是当sum特别大（天文数字）的时候，这种方案就不一定是最优解了，反而四边形不等式的方案更优
	//假设所有画完成的时间累加和为100万，10个画家，那么最优划分的情况下，全部画完的时间一定在0到100万
	//需要一个目标函数：如果所有画全部画完的时间不超过x，需要几个画家
	//例1：[2,3,1,4,2,1,3]，如果要求完成的时间不超过4，至少需要几个画家
	//这个问题可以通过遍历一遍数组得到答案：如果当前数值没有超过4，则往后扩，如果扩了超过4，则不再扩；下一个数作为开头重新考虑
	//即arr[0]=2<4，准备往后扩，发现2+3=5>4，于是不扩，所以2单独一组; 
	// arr[1] = 3 < 4，想往后扩，发现3+1=4<=4，可以扩；然后继续往后扩，发现4+4=8>4，于是不扩，所以(3,1)一组
	//以此类推。
	//类似用油桶加油，当一个桶加油超过目标值，则另用一个新桶装
	//最终可得，为达到目标，至少需要5个画家
	//例2：[2,1,5,4,2,1,3]，目标时间为4，则需要无穷多个画家，因为单独的一个值 arr[2]=5>4，无法完成
	//
	//也就是是说，对于画数组，如果给定一个目标x，则遍历一边数组就能知道至少需要几个画家
	//那么先将画数组arr的所有值累加，假设累加和为100万，而给定的画家数量为7；
	//然后在0~100万进行二分，得到50万，将50万作为目标，遍历数组看需要多少个画家；
	//假设需要4个，4<7，于是在50万处标记📌 √，继续往左进行二分，即在0~50万二分；
	//假设25万的时候还是需要4个画家，这个值的地方📌 √，表示答案可以更好，于是继续往左二分；
	//假设在10万的时候发现至少需要9个画家，9>7，在此处标记📌 x，接下来在10万+1 ~ 25万之间进行二分
	//也就是说如果在某个值发现需要的画家数量 <= 给定的画家数量，则继续往左二分；
	//如果某个值需要的画家数量 > 给定的画家数量，则往右到上一个标记的位置进行二分。最后一个📌 √ 的值就是最终答案
	public static int splitArray3(int[] nums, int M) {
		long sum = 0; //使用long以防溢出
		//1.计算所有时间的累加和
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i]; 
		}
		long l = 0;
		long r = sum;
		long ans = 0;
		while (l <= r) { //二分，答案一定在0~sum之间
			long mid = (l + r) / 2;
			long cur = getNeedParts(nums, mid);
			if (cur <= M) {  
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return (int) ans;
	}
	
	//完成arr数组中的所有画作目标时间为aim，返回至少需要几个画家
	//就是遍历一遍数组，将数组分成几个符合条件的组
	public static int getNeedParts(int[] arr, long aim) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > aim) { //单独的某个值就已经超过了目标值，不可能完成
				return Integer.MAX_VALUE;
			}
		}
		int parts = 1; //arr[0]暂且作为第1个部分
		int all = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (all + arr[i] > aim) { //尝试往右扩，发现大于目标，于是后一个数作为新的一组的第一个继续尝试
				parts++;
				all = arr[i];
			} else {
				all += arr[i];
			}
		}
		return parts;
	}

	public static int[] randomArray(int len, int maxValue) {
		int[] arr = new int[len];
		for (int i = 0; i < len; i++) {
			arr[i] = (int) (Math.random() * maxValue);
		}
		return arr;
	}

	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int N = 100;
		int maxValue = 100;
		int testTime = 10000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * N) + 1;
			int M = (int) (Math.random() * N) + 1;
			int[] arr = randomArray(len, maxValue);
			int ans1 = splitArray1(arr, M);
			int ans2 = splitArray2(arr, M);
			int ans3 = splitArray3(arr, M);
			if (ans1 != ans2 || ans1 != ans3) {
				System.out.print("arr : ");
				printArray(arr);
				System.out.println("M : " + M);
				System.out.println("ans1 : " + ans1);
				System.out.println("ans2 : " + ans2);
				System.out.println("ans3 : " + ans3);
				System.out.println("Oops!");
				break;
			}
		}
		System.out.println("测试结束");
	}
}

6、四边形不等式技巧注意点

  1. 不要证明！用对数器验证！
  2. 枚举的时候面对最优答案相等的时候怎么处理？用对数器都试试！
  3. 可以把时间复杂度降低一阶
    • O ( N 3 ) O(N^3) O(N3) -> O ( N 2 ) O(N^2) O(N2)
    • O ( N 2 ∗ M ) O(N^2 * M) O(N2∗M)-> O ( N ∗ M ) O(N * M) O(N∗M)
    • O ( N ∗ M 2 ) O(N * M^2) O(N∗M2) -> O ( N ∗ M ) O(N * M) O(N∗M)
  4. 四边形不等式有些时候是最优解，有些时候不是 【不是的原因：尝试思路，在根儿上不够好】

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/413.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

金三银四最近一次面试，被阿里P8测开虐惨了...

金三银四最近一次面试，被阿里P8测开虐惨了...

都说金三银四涨薪季&#xff0c;我是着急忙慌的准备简历——5年软件测试经验&#xff0c;可独立测试大型产品项目&#xff0c;熟悉项目测试流程...薪资要求&#xff1f;5年测试经验起码能要个20K吧 我加班肝了一页半简历&#xff0c;投出去一周&#xff0c;面试电话倒是不少&a…
阅读更多...
javaSE系列之继承与多态

javaSE系列之继承与多态

&#x1f497; &#x1f497; 博客:小怡同学 &#x1f497; &#x1f497; 个人简介:编程小萌新 &#x1f497; &#x1f497; 如果博客对大家有用的话&#xff0c;请点赞关注再收藏 &#x1f31e; javaSE系列之继承与多态继承关键字extends父类与子类在子类中访问父类的成员变…
阅读更多...
【c++】继承

【c++】继承

目录 一、继承的表现 子类对父类成员的访问权限 二、父类与子类之间的相互赋值 三、继承的作用域 如果是父类和子类构成隐藏呢&#xff1f; 四、子类的成员函数怎么写 1.default构造函数 2.析构函数 所以析构函数不需要我们显式调用。 五、继承与友元函数 六、继承与静…
阅读更多...
记录使用chatgpt的复杂经历

记录使用chatgpt的复杂经历

背景 由于最近要写论文&#xff0c;c站的gpt也变样了&#xff0c;无奈之下和同学借了一个gpt账号&#xff0c;才想起没有npv&#xff0c;不好意思去要&#xff0c;也不想买&#xff0c;于是我找了很多临时免费的直到我看到有一家&#xff0c;邀请10人即可&#xff0c;而且只用…
阅读更多...
力扣-股票的资本损益

力扣-股票的资本损益

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;1393. 股票的资本损益二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他…
阅读更多...
码农饭碗不保——ChatGPT正在取代Coder

码农饭碗不保——ChatGPT正在取代Coder

码农饭碗不保——ChatGPT正在取代Coder 最近被OpenAI的ChatGPT刷屏了。我猜你已经读了很多关于ChatGPT的文章&#xff0c;不需要再介绍了。假如碰巧您还不太了解ChatGPT是什么&#xff0c;可以先看一下这篇文章&#xff0c;然后再回来继续。 与ChatGPT对话很有趣&#xff0c;…
阅读更多...
GPT4论文翻译 by GPT4 and Human

GPT4论文翻译 by GPT4 and Human

GPT-4技术报告解读 文章目录GPT-4技术报告解读前言&#xff1a;摘要1 引言2 技术报告的范围和局限性3 可预测的扩展性3.1 损失预测3.2 人类评估能力的扩展4 能力评估4.1 视觉输入 !!!5 限制6 风险与缓解&#xff1a;7 结论前言&#xff1a; 这篇报告内容太多了&#xff01;&am…
阅读更多...
【MySQL基础】13—变量、流程控制、游标和触发器

【MySQL基础】13—变量、流程控制、游标和触发器

⭐⭐⭐⭐⭐⭐ Github主页&#x1f449;https://github.com/A-BigTree 笔记链接&#x1f449;https://github.com/A-BigTree/Code_Learning ⭐⭐⭐⭐⭐⭐ 如果可以&#xff0c;麻烦各位看官顺手点个star~&#x1f60a; 如果文章对你有所帮助&#xff0c;可以点赞&#x1f44d;…
阅读更多...
金丹一层 —— 深度刨析简单问题

金丹一层 —— 深度刨析简单问题

目录 前言&#xff1a; 深度刨析问题 前言&#xff1a; 1.CSDN由于我的排版不怎么好看&#xff0c;我的有道云笔记比较美观&#xff0c;请移步有道云笔记 2.修炼必备 1&#xff09;入门必备&#xff1a;VS2019社区版&#xff0c;下载地址&#xff1a;Visual Studio 较旧的下…
阅读更多...
Python基础—面向对象(超详版)

Python基础—面向对象(超详版)

Python基础—面向对象面向对象简介什么是面向对象类与对象父类与子类面向对象的特性单继承与多继承单继承多继承多层继承封装多态重写与调用python重写python调用super函数前言&#xff1a; &#x1f3e0;个人主页&#xff1a;以山河作礼。 &#x1f4dd;​&#x1f4dd;​此专…
阅读更多...
基于stm32智能语音电梯消毒系统

基于stm32智能语音电梯消毒系统

这次来分享个最近做的项目&#xff0c;stm32智能语音电梯消毒系统功能说明&#xff1a;在电梯&#xff0c;房间&#xff0c;客道区域内&#xff0c;检测到人&#xff0c;则执行相关动作&#xff01;例如继电器开关灯&#xff0c;喷洒酒精等行为。手机app/微信小程序可以控制需要…
阅读更多...
滑动窗口算法

滑动窗口算法

&#x1f34f;&#x1f350;&#x1f34a;&#x1f351;&#x1f352;&#x1f353;&#x1fad0;&#x1f951;&#x1f34b;&#x1f349;&#x1f95d; 啥是滑动窗口&#xff0c;它能解决什么样的问题&#xff1f; 文章目录&#x1f350;滑动窗口的概念&#x1f34f;适用场景…
阅读更多...
Docker圣经：大白话说Docker底层原理，6W字实现Docker自由

Docker圣经：大白话说Docker底层原理，6W字实现Docker自由

说在前面&#xff1a; 现在拿到offer超级难&#xff0c;甚至连面试电话&#xff0c;一个都搞不到。 尼恩的技术社群&#xff08;50&#xff09;中&#xff0c;很多小伙伴凭借 “左手云原生右手大数据”的绝活&#xff0c;拿到了offer&#xff0c;并且是非常优质的offer&#…
阅读更多...
蓝桥杯C++组怒刷50道真题

蓝桥杯C++组怒刷50道真题

&#x1f33c;深夜伤感网抑云 - 南辰Music/御小兮 - 单曲 - 网易云音乐 &#x1f33c;多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐 50题才停更&#xff0c;课业繁忙&#xff0c;有时间就更&#xff0c;2023/3/14/15:06写下 目录 &#x1f44a;填空题 &#x1f33c;一…
阅读更多...
ChatGPT作者John Schulman：我们成功的秘密武器

ChatGPT作者John Schulman：我们成功的秘密武器

来源&#xff5c;TalkRL OneFlow编译 翻译&#xff5c;杨婷、徐佳渝、贾川 除了OpenAI&#xff0c;外界可能很少有人知道ChatGPT模型成功的真正原因&#xff0c;实际上&#xff0c;OpenAI也会对ChatGPT拥有的巨大影响力感到不可思议。这种困惑和惊喜就像工程师们解bug时获得的意…
阅读更多...
在Docker上部署FastApi（最新）

在Docker上部署FastApi（最新）

目录 1 文件上传与新建目录 文件目录 2 修改requirements.txt文件 3 修改Dockerfile.txt文件 4 打包成镜像 5 运行启动 6 查看运行状态与日志 1 文件上传与新建目录 新建以下目录&#xff0c;其中.py文件是自己上传的 文件目录 新建以下文件 2 修改requirements.txt文件…
阅读更多...
关于我拒绝了腾讯测试开发岗offer这件事

关于我拒绝了腾讯测试开发岗offer这件事

2022年刚开始有了向要跳槽的想法&#xff0c;之前的公司不能算大厂但在重庆也算是数一数二。开始跳槽的的时候我其实挺犹豫的 其实说是有跳槽的想法在2022年过年的时候就有了&#xff0c;因为每年公司3月会有涨薪的机会&#xff0c;所以想着看看那能不能涨&#xff08;其实还是…
阅读更多...
RK3568平台开发系列讲解（显示篇）什么是DRM

RK3568平台开发系列讲解（显示篇）什么是DRM

🚀返回专栏总目录 文章目录 一、DRM介绍二、DRM与framebuffer的区别沉淀、分享、成长，让自己和他人都能有所收获！😄 📢本篇文章将介绍什么是DRM。 一、DRM介绍 DRM 是 Linux 目前主流的图形显示框架，相比FB架构，DRM更能适应当前日益更新的显示硬件。 比如FB原生不支…
阅读更多...
【产品经理】产品经理思维要素

【产品经理】产品经理思维要素

产品思维对于产品经理来说十分重要&#xff0c;能够有效提升工作效率和工作质量。本文作者分享了有关产品经理思维要素的相关内容&#xff0c;从思维误区、思维方式建议、理性思维探讨展开分析&#xff0c;一起来学习一下吧&#xff0c;希望对你有帮助。 一、简述 1. 背景 先…
阅读更多...
【C++】模板（上）

【C++】模板（上）

文章目录1、泛型编程2、函数模板函数模板的实例化模板参数的匹配原则3、 类模板类模板的实例化1、泛型编程 void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left …
阅读更多...
最新文章

Copyright @ 2022~2023