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:
代码语言：javascript复制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:
代码语言：javascript复制Input: nums = [1,2,3,4,5], m = 2
Output: 9Example 3:
代码语言：javascript复制Input: nums = [1,4,4], m = 3
Output: 4Constraints:
1 <= nums.length <= 10000 <= 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)。
代码：
代码语言：javascript复制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
}
