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;
    }

}