410. Split Array Largest Sum

https://leetcode.com/problems/split-array-largest-sum/

对由非负数组成的数组划分成给定的m份，最小化和最大的子数组。解这种给定背包数，找能把物品（质量值为正数）一一全部放进去的背包最小容量的题用二分最快。对每个二分mid时检查mid是否能让数组在m次分完，当需要的次数大于D时说明mid取小了，start + 1。

/*
 * @lc app=leetcode id=410 lang=cpp
 *
 * [410] Split Array Largest Sum
 */
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        const auto check = [](vector<int>& weights, long mid) {
            long sum = 0, c = 1;
            for (int w : weights) {
                if (sum + w > mid) {
                    sum = 0;
                    ++c;
                } 
                sum += w;
            }
            return c;
        };
        long start = 1, end = 1;
        for (int w : nums) {
            start = max(start, (long) w);
            end += w;
        }
        while (start < end) {
            long mid = start + (end - start) / 2;
            if (m < check(nums, mid)) {
                start = mid + 1;
            } else {
                end = mid;
            }    
        }
        return start;
    }
};

partition + optimal用DP。action为对让当前num[j]分别和不同的前面的元素k组成一个划分[k+1, j]，受限于前面的划分数目。因此把划分数encoding进状态，题目所求encoding进值，dp[i][j]表示从0到j形成i个划分的最优解，前面[0, k]有i - 1个划分，即dp[i - 1][k]。三重循环。

代码参考了花花的。

/*
 * @lc app=leetcode id=410 lang=cpp
 *
 * [410] Split Array Largest Sum
 *
 * https://leetcode.com/problems/split-array-largest-sum/description/
 *
 * algorithms
 * Hard (42.82%)
 * Likes:    954
 * Dislikes: 53
 * Total Accepted:    53.5K
 * Total Submissions: 124.8K
 * Testcase Example:  '[7,2,5,10,8]\n2'
 *
 * 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.
 * 
 * 
 */
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        const int N = nums.size();
        vector<long> sums(N);
        sums[0] = nums[0];
        for (int j = 1; j < N; ++j) {
            sums[j] = sums[j - 1] + nums[j];
        }
        vector<vector<long>> dp(m + 1, vector<long>(N, INT_MAX));
        for (int j = 0; j < N; ++j) dp[1][j] = sums[j];
        for (int i = 2; i <= m; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));
                }
            }
        }
        return dp[m][N - 1];
    }
};