① dp[i][j] 表示前 i 个数, 分成 j 份的各自和的最小值。

那么 dp[i][j] = min(dp[k][j - 1], pre[i] - pre[k - 1]), 其中 k ∈ [j - 2, i - 1], (前 k 个数至少保证能组成 j - 1 份)

② 二分答案，check 的时候贪心即可，一个部分的和不超过 mid 的情况下，能容纳更多元素就容纳更多元素，不能则分成一个新的部分。最后如果被分成的部分数目小于等于 m，那么这个答案是可行的。

// 二分
class Solution {
public:
    int splitArray(const vector<int>& nums, int m) {
        int r = 0, l = 0;
        for(int i = 0; i < nums.size(); ++ i) {
            r += nums[i];
            l = max(l, nums[i]);
        }

        int ret = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(nums, mid, m)) {
                ret = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        return ret;
    }

private:
    bool check(const vector<int> &nums, int mid, int m) {
        int cnt = 0, sum = 0;
        for(int i = 0; i < nums.size(); ++ i) {
            if(sum + nums[i] <= mid) {
                sum += nums[i];
            } else {
                ++ cnt;
                sum = nums[i];
            }
        }
        ++ cnt;     // 最后一部分余留的
        return cnt <= m;
    }
};

 

// dp
class Solution {
public:
    int splitArray(const vector<int>& nums, int m) {
        // dp[i][j] 表示 [0, i] 数, 分成 j 份, 各自和的最小值
        vector<int> preSum;    // 前缀和, preSum[i + 1] 表示 0~i 的和
        for(int i = 0; i < nums.size(); ++ i) {
            if(i == 0) preSum.emplace_back(0);
            preSum.emplace_back(preSum.back() + nums[i]);
        }

        vector<vector<int>> dp(nums.size(), vector<int>(m + 1, INT_MAX));
        for(int i = 0; i < nums.size(); ++ i) {
            for(int j = 1; j <= m; ++ j) {
                // 前 k 个数至少组成 j - 1 份
                for(int k = j - 2; k < i; ++ k) {   // [k + 1, i] 分成一份, preSum[i] - preSum[k], 然后做 1 个单位偏移量
                    if(k == -1) {   // [0, i] 成一组
                        dp[i][j] = preSum[i + 1] - preSum[k + 1];
                        continue;
                    }
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], preSum[i + 1] - preSum[k + 1]));
                }
            }
        }
        return dp.back().back();
    }
};