题目描述
给定一个非负整数数组和一个整数m，你需要将这个数组分成m个非空的连续子数组。设计一个算法使得这m个子数组各自和的最大值最小。
注意:
数组长度n满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
输入：
nums = [7,2,5,10,8]
m = 2
输出：
18
解释：
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5]和[10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
思路：
dp[i][j]表示前i个数字分成j段时各自和的最大值最小为dp[i][j]，很容易想到初始情况dp[i][1]为nums[1]+nums[2]+....+nums[i]。
更为一般的情况，想求dp[i][j]，可以考虑将使用k将前i个数字分成0~k，k~i两部分，k~i为最后一段，这时各段和最大值则为dp[k][j-1]与k~i这段和中较大者。k~i这段的和为dp[i][1]-dp[k][1]。遍历k从0到i-1，从中选择最小的一个作为dp[i][j]的值。最终返回dp[len-1][m]就是答案。
代码：
class Solution {
public int splitArray(int[] nums, int m) {
int len = nums.length;
int[][] dp = new int[len][m+1];
dp[0][1] = nums[0];
for (int i=1; i<len; i++){
dp[i][1] = dp[i-1][1] + nums[i];
}
for (int i=0; i<len; i++){
for (int j=2; j<=m; j++){
int minSumMax = Integer.MAX_VALUE;
for (int k=0; k<i; k++){
minSumMax = Math.min(minSumMax , Math.max(dp[k][j-1], dp[i][1]-dp[k][1]));
}
dp[i][j] = minSumMax ;
}
}
return dp[len-1][m];
}
}
