leetcode410

题目

Leetcode 410

此题非常自然的想法就是动态规划，但是用C++一交，只能打败20%的人，说明时间内存双双爆炸，查看题解后，竟然还有一种神奇的二分做法（虽然之前暑假集训见过，但是仍然很巧妙）；

又是被每日一题杀烂的一天

动态规划

先来看看暴力的动态规划：

维护数组，代表数组个数分成组的最佳方案；

注意到分组的无后效性，即存在对于某一个边界下标,分成组可以看成分成组以及单独构成一组，但是这里要满足，前面的分组情况不会影响后一组的元素之和；

我们贪心地确定分割的最后一个下标（称为凤尾），对于枚举凤尾的所有可能情况，找到最佳的凤尾，极小化分割数组和最大值，从后向前确定凤尾，最终整个分割的情况被确定；

若是凤尾的一个备选值，而假如凤尾前的分割最佳情况已经确定，分割数组和最大值为,现遍历,不断更新使得保持为最小状态，也就找到了动态规划方程：

贴下暴力做法的代码：

class Solution {
public:
    int f[1005][55];
    int inf=1000000007;
    int splitArray(vector<int>& nums, int k) {
        memset(f,0,sizeof(f));
        int n= nums.size();
        for(int K=0;K<=k;++K){
            for(int N=0;N<=n;++N){
                if(K==0||N<K) f[N][K]=inf;
                else if(K==1){
                    f[N][K]=(N==1)?nums[N-1]:f[N-1][K]+nums[N-1];
                }
                else{
                    int best=inf;
                    int sum=0;
                    f[N][K]=inf;
                    for(int x=N-1;x>=0;--x){
                        sum+=nums[x];
                        if(best>max(f[x][K-1],sum)){
                            best=max(f[x][K-1],sum);
                        }
                    }
                    f[N][K]=best;
                }
            }
        }
        return f[n][k];
    }
};

三重循环表明时间复杂度为

二分查找可能答案

再来介绍下社区里一个漂亮的二分做法；

称一组段数组的分割使得所有子数组元素和不大于的分割为完美分割；

请注意，完美分割不一定是题目要求的理想状态，因为有可能等号取不到，所有子数组元素和都严格小于;

• 假如分割数组最大值的极小化结果是一个明确的答案,的一个平凡下界为,平凡上界为；

  • 很明显，对于,一定存在完美分割(它就是题目中想象的，能够达到的那个分割)，同时注意的最小性，对于,一定不存在完美分割，我们发现了其中的等价关系；

• 我们缩小这个上下界，当前为，二分区间验证是上界还是下界；

  • 准确来说，是不断尝试用缩小；
  • 如果发现存在完美分割，说明是一个比更优的上界；
  • 如果不存在完美分割，说明,改进下界为;

• 我们构造一种贪心的分割策略：保证当前子数组元素和不超过，也即往当前组加入新数，如果即将超过了就开一个新组（分割原来的旧组），新数加入到新组中；

  这样的贪心策略保证在每个子数组和不超过的前提下，划分的组数最少；

  • 如果我们发现,基于贪心策略我们很容易的能给出完美分割的策略：打散比较长的子数组，使得增加到,（这一般是很容易做到的，除非每个子数组只有一个数，但这往往说明上下界要重合了）

  • 反之若，连贪心的策略都无能为力，说明完美分割是不可能的：

    因为完美分割也在每个子数组元素和不超过的前提下，由的最小性,,矛盾；

  • 最小性证明：如果存在一种分割策略，划分了个子数组，那么在中一定存在一个子数组包含中的一个子数组未来的我一定能看懂吧，由贪心性质，这组元素和要超过,这与也是满足前提的策略矛盾

• 若完美分割存在，说明我们贪心地分割数组，保证每个子数组和不超过，也即往当前组加入新数，如果即将超过了就开一个新组，新数加入到新组中，这样的贪心策略能保证分割数组在每个子数组和不超过的前提下，划分的组数最少；

• 就这样，区间越来越小，由离散介值原理，达到时，一定有个数组元素和能取等（否则就会继续缩小）；

贴代码：

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        l = max(nums)
        r = sum(nums)
        while(l<r):
            mid = (l + r)//2
            if(self.check(nums, k, mid)):
                r = mid
            else:
                l = mid + 1
        return l
        
    def check(self, nums: List[int], k: int, val: int) ->bool:
        cnt, tmp = 1, 0
        for num in nums:
            if tmp + num<=val:
                tmp += num
            else:
                cnt +=1
                tmp = num
        return cnt<=k

给出这个算法的证明还算比较自然，但是如何能敏锐地注意到应该使用二分搜索答案（条件最大值地极小化），如何注意到一系列的等价关系确实值得好好记录xia'lai