410. 分割数组的最大值 Krains 2020-08-29 20:21:39 动态规划二分查找

class Solution {
    public int splitArray(int[] nums, int m) {
        int right = Integer.MAX_VALUE;
        int left = 0;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(canSplit(nums, m, mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        return left;
    }

    public boolean canSplit(int[] nums, int m, int sum){
        int s = 0;
        int count = 1;
        for(int num : nums){
            // 如果数组中某个数大于sum，无法完成分组
            if(num > sum)
                return false;
            // 如果num能够加入分组，则加入，否者新开一个分组
            if(s + num <= sum){
                s += num;
            }else{
                s = num;
                count++;
            }
        }

        return count <= m;
    }
}

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] preSum = new int[n+1];
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= n; i++){
            preSum[i] += preSum[i-1] + nums[i-1];
        }

        for(int i = 0; i <= m; i++){
           Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        dp[0][0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = i; j <= n; j++){
                for(int k = 0; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k], preSum[j] - preSum[k]));
                }
            }
        }

        return dp[m][n];
    }
}

class Solution {
    // 前缀和数组，因为数组和会超出int范围，因此用long
    long[] s;
    int n;

    public int splitArray(int[] nums, int m) {
        n = nums.length;
        s = new long[n+1];
        for(int i = 1; i <= n; i++){
            s[i] = s[i-1] + nums[i-1];
        }

        return (int)helper(0, 0, m, new Long[n+1][m+1]);
    }

    // [i, n)是待划分的区域，j表示当前是第几个划分点，j个划分点能够划出j+1个区域
    public long helper(int i, int j, int m, Long[][] memo){
        if(memo[i][j] != null)
            return memo[i][j];
		
        // 当j+1等于m时，划分完毕，直接返回当前区域的和
        if(j+1 == m)
            return s[n] - s[i];

        long min = Integer.MAX_VALUE;
        // 穷尽所有划分点
        for(int k = i; k < n; k++){
            // t是当前划分的组内和的最大值
            long t = Math.max(s[k+1]-s[i], helper(k+1, j+1, m, memo));
            // min是所有可能划分的组内和的最大值的最小值
            min = Math.min(t, min);
        }

        // 记忆
        return memo[i][j] = min;
    }
}