【leetcode】No.410：split-array-lar

题目描述

给定一个非负整数数组和一个整数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];
    }
}