410. 分割数组的最大值

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/split-array-largest-sum/
Star
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)

法1 动态规划 第一类区间型

思路
参考
📃
1278. 分割回文串 III
题解
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        dp = [[float('inf')] * (m+1) for _ in nums]
        
        # 初始化，分割 为 1 份 的结果
        sum_ = 0
        for i in range(0, len(nums)):
            sum_ += nums[i]
            dp[i][1] = sum_

        for i in range(0, len(nums)):
            for k in range(2, m+1):
								# 不够分 k 份了
                if i + 1 < k:
                    break

                for j in range(i, -1, -1):
										# 前面的不够分 k-1 份了
                    if j < k - 1:
                        break
                    dp[i][k] = min(dp[i][k], max(dp[j-1][k-1], sum(nums[j:i+1])))

        print(dp)
        return dp[-1][m]

法2 二分法

思路
用二分法去猜答案。
满足分割的 答案有很多，用二分的思路去寻找最想要的答案，即各分割好的数组之和的最大值最小。
所以关键在于 isValid函数的写法，用于判断当前的答案是否合格，然后再用二分的思路去逼近想要的答案。
题解
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        min_, max_ = max(nums), sum(nums)
        while min_ <= max_:
            mid = min_ + (max_ - min_) // 2
            if self.isValid(nums, m, mid):
                max_ = mid - 1
            else:
                min_ = mid + 1

        return min_

    def isValid(Self, nums, m, mid):
        cur_num = 0
        count = 1
        for n in nums:
						if n > mid:
								return False
            cur_num += n
            # 超过 每个分组各自和的最大值 ，即mid了，就可以砍一刀
            if cur_num > mid:
                count += 1
                # 分组数目超过 m 了
                if count > m:
                    return False
                cur_num = n 
        return True