29、算法与数据结构 - 实战：四边形不等式技巧
题目一
给定一个非负数组arr，长度为N，
那么有N-1种方案可以把arr切成左右两部分
每一种方案都有，min{左部分累加和，有部分累加和}
求这么多方案中，min{左部分累加和，有部分累加和}的最大值是多少？
整个过程要求时间复杂度O(N)
解法： 1、 先求出数组累加和sum；
2、 每一个位置的切分，都有左部分累加和leftSum，和有部分rightSum；
3、 一开始leftSum=0，rightSum=sum，枚举每个切分位置，leftSum不断加入数，rightSum不断减去数；
4、 每次抓一个答案min(leftSum,rightSum)去PK一下；
/**
* 给定一个非负数组arr，长度为N，
* 那么有N-1种方案可以把arr切成左右两部分
* 每一种方案都有，min{左部分累加和，有部分累加和}
* 求这么多方案中，min{左部分累加和，有部分累加和}的最大值是多少？
* 整个过程要求时间复杂度O(N)
* Created by huangjunyi on 2022/12/10.
*/
public class PostOfficeProblem_0 {
public static int splitArray(int[] arr) {
if (arr == null || arr.length < 2) return 0;
// 求出整体累加和sum
int sum = 0;
for (int num : arr) sum += num;
int max = 0;
// 左部分累加和
int leftSum = 0;
// 枚举每个切分位置
for (int i = 0; i < arr.length; i++) {
// 左部分增加进入左侧的数
leftSum += arr[i];
// 抓一个min(left,right)样本，PK一下
max = Math.max(max, Math.min(leftSum, sum - leftSum));
}
return max;
}
}
题目二
把题目一种提到的，
min{左部分累加和，有部分累加和}，定义为S(N-1)，也就是说：
S(N-1)：在arr[0…N-1]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值
现在要求返回一个长度为N的s数组，
s[i]=在arr[0…i]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值
得到整个s数组的过程，做到时间复杂度O(N)
一般想到的解法是，枚举每一个子数组结束位置，然后用题目一的方法
但是这种解法的时间复杂度是O(N^2)
这种解法存在重复计算的过程，而实际上枚举的切分位置是不需要回退的，假设我上一轮得出的最优切分位置是9，现在进入下一轮了，为什么切分位置不用回退，只要继续往右呢？
有三种情况：
1、 上一轮左部分的累加和比右部分小，进入下一轮，如果切分位置回退了，那左部分不就更小了？所以不用回退；
2、 上一轮左部分的累加和比右部分大，进入下一轮，右部分却比左部分大了，左部分比右部分小，那也不用回退，因为回退了，左部分不也是更小吗？；
3、 上一轮左部分的累加和比右部分大，进入下一轮，还是左部分的累加和比右部分大，也不用回退因为回退能得更大的答案的话，上一轮就不会再得出这个位置是最优切分位置如果回退了，右部分还是更小，但是得到的答案更大，那么上一轮就应该在前一个位置；如果回退了，左部分更小，但是得到的答案更大，那么上一轮也应该在在前一个位置，因为上一轮的前一个切分位置的左部分累加和也是这个，而右部分的累加和反而增加了，那么不管minSum是左侧还是右侧，都比切分位置往后移一位要大，而这个结论是和当前这种情况的前提是相违背的；
/**
* 把题目一种提到的，
* min{左部分累加和，有部分累加和}，定义为S(N-1)，也就是说：
* S(N-1)：在arr[0...N-1]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值
* 现在要求返回一个长度为N的s数组，
* s[i]=在arr[0...i]范围上，做最优划分所得到的min{左部分累加和，右部分累加和}的最大值
* 得到整个s数组的过程，做到时间复杂度O(N)
* Created by huangjunyi on 2022/12/10.
*/
public class PostOfficeProblem_1 {
public static int[] splitArray(int[] arr) {
if (arr == null || arr.length == 0) return new int[0];
int N = arr.length;
int[] res = new int[N];
res[0] = 0;
int leftSum = 0; // 左部分累加和
int rightSum = arr[0]; // 右部分累加和
int bestSplit = -1; // 最优划分位置，一开始是0~0范围，肯定是左边一个数也没有，右边有一个数，所以切在-1位置
for (int range = 1; range < N; range++) {
rightSum += arr[range]; // 范围扩大了
while (bestSplit + 1 < range) {
int before = Math.min(leftSum, rightSum); // 切分位置不动，min{左部分累加和，右部分累加和}
int after = Math.min(leftSum + arr[bestSplit + 1], rightSum - arr[bestSplit + 1]); // 切分位置往后挪一位, min{左部分累加和，右部分累加和}
if (after >= before) {
// 切分位置往后挪一位，结果更好
leftSum = leftSum + arr[bestSplit + 1];
rightSum = rightSum - arr[bestSplit + 1];
bestSplit++; // 切分位置往后挪一位，结果更好，就往右挪了
} else {
break;
}
}
res[range] = Math.min(leftSum, rightSum);
}
return res;
}
}
题目三
摆放着n堆石子。现要将石子有次序地合并成一堆
规定每次只能选相邻的2堆石子合并成新的一堆，
并将新的一堆石子数记为该次合并的得分
求出将n堆石子合并成一堆的最小得分（或最大得分）合并方案
这一题可以用范围尝试模型对应的dp解
dp[L][R]表示从L~R范围上，最优合并方案的最小代价
假设，arr = [1,4,2,3]
dp表的两条对角线可以填好
下半部分是没有用的，因为L>R
那么其他格子怎么求呢？
比如求dp[1][3]，也就是1~3范围的最右合并方案的最小代价
其实看最后一次合并时的最优划分方案，就转换成了上一题的问题
1~1和2~3合并，1~2和3~3合并
所以求dp[1][3]，就看dp[1][1]+dp[2][3]、dp[1][2]+dp[3][3]，谁更小，再加一个1~3范围的累计和
dp[0][3]同理，0~0和1~3合并，0~1和2~3合并，0~2和3~3合并
public static int mergeStone(int[] arr) {
if (arr == null || arr.length < 2) return 0;
int N = arr.length;
// 初始化dp表的两条对角线，因为dp[i][i]对角线本来就是0，所以不用管
int[][] dp = new int[N][N];
for (int i = 0; i < N - 1; i++) {
dp[i][i + 1] = arr[i] + arr[i + 1];
}
// 求一个前缀和数组，后面要用到
int[] preSum = new int[N];
preSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
preSum[i] = preSum[i - 1] + arr[i];
}
/*
dp[L][R]表示从L~R范围上，最优合并方案的最小代价
枚举最后一次合并的切分方案
比如dp[0][3]，0~3范围最优合并方案的最小代价
最后一次合并的切分方案就有：
0~0和1~3合并，0~1和2~3合并，0~2和3~3合并
所以dp[0][3] = min(dp[0][0]+dp[1][3], dp[0][1]+dp[2][3], dp[0][2]+dp[3][3]) + sum(arr, 0, 3)
*/
for (int L = N - 3; L >= 0; L--) {
for (int R = L + 2; R < N; R++) {
dp[L][R] = Integer.MAX_VALUE;
for (int split = L; split < R; split++) {
dp[L][R] = Math.min(dp[L][R], dp[L][split] + dp[split + 1][R]);
}
// + sum(arr, L, R)
dp[L][R] = dp[L][R] + preSum[R] - (L == 0 ? 0 : preSum[L - 1]);
}
}
// 从0~N-1范围上，最优合并方案的最小代价
return dp[0][N - 1];
}
但是这样子，在求每个格子时就要枚举行为
而且枚举的是切分位置，那是不是可以像上一题一样，保存上一轮的切分位置，这一轮就不用回退了？
所以再搞一个bestSplit[][]
bestSplit[L][R]表示的是在求dp[L][R]时的最优切分位置
public static int mergeStone2(int[] arr) {
if (arr == null || arr.length < 2) return 0;
int N = arr.length;
// 初始化dp表和bestSplit表的两条对角线，因为dp[i][i]对角线本来就是0，bestSplit[i][i]只有一个数，也没得切，所以不用管
int[][] dp = new int[N][N];
int[][] bestSplit = new int[N][N];
for (int i = 0; i < N - 1; i++) {
dp[i][i + 1] = arr[i] + arr[i + 1];
bestSplit[i][i + 1] = i;
}
// 求一个前缀和数组，后面要用到
int[] preSum = new int[N];
preSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
preSum[i] = preSum[i - 1] + arr[i];
}
/*
dp[L][R]表示从L~R范围上，最优合并方案的最小代价
枚举最后一次合并的切分方案
比如dp[0][3]，0~3范围最优合并方案的最小代价
最后一次合并的切分方案就有：
0~0和1~3合并，0~1和2~3合并，0~2和3~3合并
所以dp[0][3] = min(dp[0][0]+dp[1][3], dp[0][1]+dp[2][3], dp[0][2]+dp[3][3]) + sum(arr, 0, 3)
bestSplit[L][R]表示的是在求dp[L][R]时的最优切分位置
用于优化枚举行为，切分位置不用回退
*/
for (int L = N - 3; L >= 0; L--) {
for (int R = L + 2; R < N; R++) {
dp[L][R] = Integer.MAX_VALUE;
// 切分位置在上一轮的基础上往后尝试
int best = bestSplit[L][R - 1];
// 当前L~R的最优切分位置，肯定在getBestSplit(L, R-1)和getBestSplit(L+1, R)之间
// 所以就在bestSplit[L][R - 1]~bestSplit[L + 1][R]之间
for (int split = bestSplit[L][R - 1]; split <= bestSplit[L + 1][R]; split++) {
if (dp[L][split] + dp[split + 1][R] < dp[L][R]) {
dp[L][R] = Math.min(dp[L][R], dp[L][split] + dp[split + 1][R]);
best = split; // 更新切分位置
}
}
// + sum(arr, L, R)
dp[L][R] = dp[L][R] + preSum[R] - (L == 0 ? 0 : preSum[L - 1]);
// 记录最优切分位置
bestSplit[L][R] = best;
}
}
// 从0~N-1范围上，最优合并方案的最小代价
return dp[0][N - 1];
}
这种优化区间范围划分的技巧，就是四边形不等式技巧
四边形不等式技巧
1、 两个可变参数的区间划分问题；
2、 每个格子有枚举行为；
3、 当两个可变参数固定一个，另一个参数和答案之间存在单调关系；
4、 而且往往是反向单调关系；
5、 枚举加速的位置对：上+右，或者，左+下；
6、 不要证明！用对数器验证！；
7、 可以把时间复杂度降低一阶；
题目四
力扣第410题
https://leetcode.cn/problems/split-array-largest-sum/
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释： 一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
其实这个题目也可以转化为一个二维区间划分问题，怎么转化为区间二维划分问题呢？
假设现在要求L~R范围内，划分为m个子数组，各划分方案下各子数组累加和中最大值中的最小值
就看前m-1个子数组和最后一个子数组，怎么切分，枚举切分位置
那么m-1个子数组的答案怎么求呢？前m-2个子数组和第m-1个子数组，怎么切分，枚举切分位置
所以搞一个二维dp表
dp[i][j]表示从数组0~i位置，分成j个子数组，各子数组累加和中最大值中的最小值
dp[i][j]中的leftMax就枚举dp[i][j-1]、dp[i-1][j-1]、dp[i-2][j-1]、…，rightSum则通过前缀和数组求，dp[i][j] = min(dp[i][j], min(leftMax, rightSum))
class Solution {
public int splitArray(int[] nums, int k) {
int N = nums.length;
int[][] dp = new int[N][k + 1];
// 初始化dp表第0行，0~0范围，分i个子数组，最大的累加和
for (int i = 1; i <= k; i++) {
dp[0][i] = nums[0];
}
// 初始化dp表第0列，0~i范围，分0个子数组，最大的累加和，无效，不用管
// 初始化dp表第1列，0~i范围，分1个子数组，最大的累加和，其实就是nums数组前缀和，可以同时把前缀和数组生成好，反正后面要用
int[] preSum = new int[N];
preSum[0] = nums[0];
dp[0][1] = preSum[0];
for (int i = 1; i < N; i++) {
preSum[i] = preSum[i - 1] + nums[i];
dp[i][1] = preSum[i];
}
/*
dp[i][j]:
从0~i，分j个子数组，子数组各自累加和中的最大值，中的最小值（最优划分方案下）
0~i，切2部分，左部分前j-1个子数组分，后一部分给最后一个数组
而左部分前j-1个子数组划分的答案，之前已经求过
dp[i][j] = min(max(dp[0][j-1], rightSum), max(dp[1][j-1], rightSum), max(dp[2][j-1], rightSum), ......)
*/
for (int i = 1; i < N; i++) {
for (int j = 2; j <= k; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int split = 0; split < i; split++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[split][j - 1], preSum[i] - preSum[split]));
}
}
}
// 在0~N-1范围上分k个子数组，子数组各自累加和中的最大值，在最右划分方案下的最小值
return dp[N - 1][k];
}
}
然后可以在上面的解法基础上，使用四边形不等式优化
另外准备一个bestSplit[][]表，bestSplit[i][j]存求dp[i][j]是的最优切分位置
但是要修改一些填dp表的顺序，整体上从左往右填，每一列从下往上填
class Solution {
public int splitArray(int[] nums, int k) {
int N = nums.length;
int[][] dp = new int[N][k + 1];
// split[i][j]存求dp[i][j]是的最优切分位置
int[][] bestSplit = new int[N][k + 1];
for (int i = 1; i <= k; i++) {
dp[0][i] = nums[0];
// 0~0范围，分i分，只有1个数可以分
bestSplit[0][i] = 0;
}
int[] preSum = new int[N];
preSum[0] = nums[0];
dp[0][1] = preSum[0];
// 0~0范围，分1分，只有1个数可以分
bestSplit[0][1] = 0;
for (int i = 1; i < N; i++) {
preSum[i] = preSum[i - 1] + nums[i];
dp[i][1] = preSum[i];
// 0~i范围，分1分，那就是不用分，切分为在-1
bestSplit[i][1] = -1;
}
// 整体一列一列从左往右填
for (int j = 2; j <= k; j++) {
// 单独一列从下往上填，用四边形不等式优化
for (int i = N - 1; i >= 1; i--) {
dp[i][j] = Integer.MAX_VALUE;
// 最优切分位置，只在bestSplit[i][j - 1]和bestSplit[i +1][j]中间范围枚举
int best = bestSplit[i][j - 1] == -1 ? 0 : bestSplit[i][j - 1];
for (int split = best; split <= (i < N - 1 ? bestSplit[i + 1][j] : N - 1); split++) {
int leftMin = split == -1 ? 0 : dp[split][j - 1];
int rightSum = split == i ? 0 : preSum[i] - preSum[split];
if (Math.max(leftMin, rightSum) < dp[i][j]) {
// 这里 <? 还是 <=?，是一个边界条件，不同题目是不一样的，要都试一下
dp[i][j] = Math.max(leftMin, rightSum); // 切分位置往右挪，结果更好
best = split; // 更新最优切分位置
}
}
bestSplit[i][j] = best; // 保存最优切分位置
}
}
return dp[N - 1][k];
}
}
题目五
一条直线上有居民点，邮局只能建在居民点上。给定一个有序正数数组arr，每个值表示居民点的一维坐标，再给定一个正数num，表示邮局数量。选择num个居民点建立num个邮局，使所有的居民点到最近邮局的总距离最短，返回最短的总距离。
【举例】
arr= [1,2,3,4,5,1000]，num = 2
第一个邮局建立在3位置，第二个邮局建立在1000位置。那么1位置到邮局的距离为2，2位置到邮局距离为1，3位置到邮局距离为0，4位置到邮局的距离为1，5位置到邮局的距离为2，1000位置到邮局的距离为0。这种方案下的总距离为6，其他任何方案的总距离都不会比该方案的总距离更短，所有返回6
没有使用四边形不等式优化时的版本：
public static int minDis(int[] arr, int num) {
/*
生成一个N行N列二维数组record，recode[i][j]表示i~j范围上建一个邮局，最短距离是多少
生成一张N行num列二维表dp，dp[i][j]表示0~i号居民点，建立j个邮局，最短距离是多少
dp表的生成依赖到recode表
*/
if (arr == null || arr.length < 2 || num < 1) return 0;
int[][] recode = getRecode(arr);
int N = arr.length;
int[][] dp = new int[N][num + 1];
/*
dp表第0列不用填，0个邮局，距离无限大
dp表第0行不用填，1个居民点，距离都是0
先初始化第1列
*/
for (int i = 0; i < N; i++) {
dp[i][1] = recode[0][i];
}
/*
填剩下的
j大于等于i的也不用填
因为那表示邮局数量最少和居民点一样多
那就一人一个，距离为0
*/
for (int i = 1; i < N; i++) {
for (int j = 2; j <= Math.min(i, num); j++) {
// 初始化dp[i][j]，表示0~i居民点都由最后一个邮局负责
dp[i][j] = recode[0][i];
// 枚举最后一个居民点的负责范围 k ~ i <= 这里存在枚举行为，可以用四边形不等式优化
for (int k = i; k > 0; k--) {
dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + recode[k][i]);
}
// 还有一个是0~i范围，都由前j-1个邮局负责，最后一个邮局歇菜，不过也不可能
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
}
}
return dp[N - 1][num];
}
private static int[][] getRecode(int[] arr) {
/*
每次都假设邮局正处于范围的中间
就recode[L][R]时，就是L~R-1范围的距离recode[L][R - 1]，加上新增居民点离邮局的距离
只需要填上半部分，下半部分不需要填，因为L不可能大于R
*/
int N = arr.length;
int[][] recode = new int[N][N];
for (int L = 0; L < N; L++) {
for (int R = L + 1; R < N; R++) {
recode[L][R] = recode[L][R - 1] + arr[R] - arr[(L + R) >> 1];
}
}
return recode;
}
使用四边形不等式技巧优化后的版本：
/**
* 给定一个数组arr，arr为正整数有序数组，代表居民点坐标
* 再给定一个正整数num，代表邮局数量
* 邮局可以建在任意居民点上
* 求邮局离居民点的最短距离
*
* 用四边形不等式优化枚举行为
* 只要符合三种情况：
* 1）存在枚举行为
* 2）每个格子和它上、右或下、左存在某种单调关系
* 3）是一个区间划分问题
* 就可以用四边形不等式尝试优化，优化的时枚举行为，缩短枚举行为的范围
* 用一个choose[i][j]记录dp[i][j]是枚举行为最优取值的枚举值k
* 下次填其他格子时就可以通过choose记录的当时获得最优值的枚举值，作为其枚举行为的上界或下界，缩短枚举行为的范围
*
* 还有第四个条件
* 4）dp[i][j]不会同时依赖本行和本列的某个值或某些值，即最多只会依赖本行某个值或本列某个值，或者都不依赖
* 比如只依赖本列的值，那就从上往下填，然后在从右往左，一个格子就依赖上一个格子和右边格子得出枚举k的上下界
* 比如只依赖本行的值，那就从左往右填，然后从下往上填，一个格子就依赖左边格子和下以边格子得出枚举k的上下界
* 比如只依赖左边和左上方的左右格子，但不依赖本列，可以先填好第一个列，然后从第二列最底下一个格子从下往上，从左往右填，一个格子就依赖左边和下边格子得出枚举k的上下界
*
* 优化的原理：
* 比如：在数组上切一刀，求min(max(leftSum, rightSum))
* 如果数组在0~N范围上切一刀，切在i位置
* 现在数组长度加1，求0~N+1，那么其实不需要从0开始尝试，从i开始即可
* 因为0~N和0~N+1是存在某种单调关系的
* 0~N在i位置且一刀是最优解
* 如果0~N+1在i左边的位置切一刀，肯定不是最优解，因为rightSum会更大
*
* Created by huangjunyi on 2022/10/15.
*/
public class _02PostOfficeProblem {
public static int minDis(int[] arr, int num) {
/*
生成一个N行N列二维数组record，recode[i][j]表示i~j范围上建一个邮局，最短距离是多少
生成一张N行num列二维表dp，dp[i][j]表示0~i号居民点，建立j个邮局，最短距离是多少
dp表的生成依赖到recode表
*/
if (arr == null || arr.length < 2 || num < 1) return 0;
int[][] recode = getRecode(arr);
int N = arr.length;
int[][] dp = new int[N][num + 1];
/*
dp表第0列不用填，0个邮局，距离无限大
dp表第0行不用填，1个居民点，距离都是0
先初始化第1列
*/
for (int i = 0; i < N; i++) {
dp[i][1] = recode[0][i];
}
/*
有一个N行N列的二维表，记录填dp[i][j]是，k当时的值是多少
那么在填一个格子的时候，枚举k的范围，就有一个下界和上界
k的下界就是它上一个格子的k的取值，下界就是它右边一个格子的取值
*/
int[][] choose = new int[N][N];
/*
填剩下的
j大于等于i的也不用填
因为那表示邮局数量最少和居民点一样多
那就一人一个，距离为0
*/
for (int i = 1; i < N; i++) {
for (int j = Math.min(i, num); j >= 2; j--) {
int down = choose[i - 1][j]; // 枚举k时的下界
int up = j == Math.min(i, num) ? i : choose[i][j + 1]; // 枚举k时的上界
// 初始化dp[i][j]，表示0~i居民点由一个邮局负责
dp[i][j] = recode[0][i];
// 枚举最后一个居民点的负责范围 k ~ i <= 这里用四边形不等式优化，枚举范围从1~i缩短到从down~up
for (int k = Math.max(1, down); k <= Math.min(i, up); k++) {
if (dp[k - 1][j - 1] + recode[k][i] < dp[i][j]) {
dp[i][j] = dp[k - 1][j - 1] + recode[k][i];
choose[i][j] = k;
}
}
}
}
return dp[N - 1][num];
}
private static int[][] getRecode(int[] arr) {
/*
每次都假设邮局正处于范围的中间
就recode[L][R]时，就是L~R-1范围的距离recode[L][R - 1]，加上新增居民点离邮局的距离
只需要填上半部分，下半部分不需要填，因为L不可能大于R
*/
int N = arr.length;
int[][] recode = new int[N][N];
for (int L = 0; L < N; L++) {
for (int R = L + 1; R < N; R++) {
recode[L][R] = recode[L][R - 1] + arr[R] - arr[(L + R) >> 1];
}
}
return recode;
}
}