410. 分割数组的最大值

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10<sup>6</sup>
• 1 <= m <= min(50, nums.length)

分析

这是动态规划中很经典的划分问题，和1335题的任务调度问题很相似，都是给一个集合，让你划分成XXX，然后给你一个规则来找出这个规则下的最优解。

• 解决动态规划，最重要的就是明确子问题，找到状态转移方程，明确初始条件，基本就完成了。
• 仔细分析这道题，给定一个数组nums[i] (0 <= i <= n)，让你划分为m分，然后求m分中和值最大的划分方式中的最小值。
• 很明显子问题是对于一个数组nums[i] (0 <= i <= n-1)，前i位数组划分为m-1分，然后求m-1分中和值最大的划分方式中的最小值。
• 那就可以使用一个备忘录，dp[n][m] 来表示 把n个数 m分中和值最大的划分方式中的最小值。对可以用变量k对n个数进行枚举 ，其中前 k个数被分割为 m-1 段，而第 k+1到 n 个数为第 m 段。第 m 段的和值可以用前缀和的方式以O(1)的时间复杂度获得。
• 求m-1段的最大值就是： max(dp[k][m-1], sub(k + 1, n)
  状态转移方程就是dp[n][m] = min(dp[n][m], maxValue), maxValue = max(dp[k][m-1], sub(k + 1, n) (0 <= k < n)。

代码：

func splitArray(nums []int, m int) int {
    n := len(nums)
    dp := make([][]int, n + 1)
    sub := make([]int, n + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, m + 1)
        for j := 0; j < len(dp[i]); j++ {
            dp[i][j] = 1 << 31 - 1
        }
    }

    // 前缀和加速
    for i := 0; i < n; i++ {
        sub[i + 1] = sub[i] + nums[i]
    }
    
    dp[0][0] = 0
    for i := 1; i <= n; i++ {
        // 从分成1份开始，一直到分成m份
        for j := 1; j <= m; j++ {
            // 然后看前k个数，分成j-1份,
            // 就是前半部分的解（备忘录已经算好），和最后一部分的和值（前缀和）比较，来做状态转移
            for k := 0; k < i; k++ {
                // sub[i] - sub[k] 使用前缀和，快速求出最后一段的和值
                dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]))
            }
        }
    }
    return dp[n][m]
}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}