LeetCode 410. Split Array Largest Sum

1.题目

410. Split Array Largest Sum

Given an array 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.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

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.

题目大意：给出一个数组nums和一个数字m，要求将nums数组划分成m个不空的子数组，返回所有划分中 元素之和最大分组的最小值

2.解题思路

   像其他动规问题一样，此题的中心思路是将大分组数m 向小的分组数m-1进行转换
   1.子问题划分
         将划分成m组的问题想象成在已经划分成m-1组的基础之上再从中选择一组划分，即分成m组 <=> m-1组（已计算好） + 1组（可求） 
   dp[i][j] i=1,..,m  j=1,..,len 表示前j个字符分成i组，最大组的元素之和出现的所有情况中    最大和的最小值
   
   2.递推公式 
   1）预先准备：先设数组sum[i] i=1,...,len; sum[i]表示前i个数的和；
   2）初值:dp[1][j] = sum[j],即前j个数只分成一个组，其最大值是唯一的 就是前j个元素之和；
   3）递推式：dp[i][j] = min{dp[i][j],max{m[i-1][k],sum[j]-sum[k]}}
                其中  2<=i<=k, i<=j<=len, i-1<=k<j；
               （1）k是游标，遍历所有j个元素的不同划分方法，求出所有最大组元素和中最小的那组，并将其赋值给dp[i][j]
               （2）max比较是为了找出当前划分方法中的最大组， 即比较上一轮划分的m-1组中最大和值 与 当前抛开前m-1组划分的剩下元素的和值 ，更大的即可代表当前和值
   
   3.输出
   dp[m][len]

3.JAVA代码

   public  int splitArray(int[] nums, int m) {
    	int len = nums.length;
    	int sum[] = new int[len+1];
    	if(len == 1){
    		return nums[0];
    	}
    	int dp[][] = new int[len+1][len+1];
    	//为sum赋值
		for(int i=1;i<=len;i++){
			sum[i] = sum[i-1] + nums[i-1];
			dp[1][i] = sum[i];
		}
    	//dp[i][j]:前j个字符分成i组，最大组的元素之和出现的所有情况中    最大和的最小值
    	for(int i=2;i<=m;i++){
    		for(int j=i;j<=len;j++){
    			dp[i][j] = Integer.MAX_VALUE;//初始化附上最大值
    			//遍历所当前有分组方式，并找出目标值
    			for(int k=i-1;k<j;k++){
    				int q = Math.max(dp[i-1][k], sum[j]-sum[k]);
    				dp[i][j] = Math.min(dp[i][j], q);
    			}
    		}
    	}
		return dp[m][len];
    }