LeetCode 410 分割数组的最大值(二分,dp)

给定一个非负整数数组和一个整数 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，在所有情况中最小。

思路

方案一：二分

枚举满足题意的和的最大值，每一次check按照贪心原则最大化分段，如果最后分段出来的段的数量大于0，代表右区间可以缩小，反之左区间增大。

时间复杂度：$O(n*log(sum-max_n))$

方案二：dp

定义 dp[i][j]表示把前$i$个数分成$j$段，所能达到的段内和的最大值最小的值。

则考虑第 j段的范围，可以枚举k，把第 j段分为：[0,k]和 [k+1,j]这两段，则 dp[i][j]的值就等于 [0,k]这一段的最优解的值与 [k+1,j]这一段的和的最大值，枚举k，使这个值最小即可，即：

$ dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]))$

对于 [k+1,j]这一段的和，可以预处理出前缀和，直接做减法得到。

时间复杂度：$O(n^2m)$

代码

方案一：二分代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
    bool check(vector<int> &nums, int m, int target)
    {
        long long i = 0, sum = 0;
        while (i < nums.size())
        {
            if (nums[i] > target)
                return false;
            if (sum + nums[i] > target)
            {
                m--;
                sum = 0;
                continue;
            }
            sum += nums[i++];
        }
        if (m > 0)
            return true;
        return false;
    }
    int splitArray(vector<int> &nums, int m)
    {
        long long sum = 0;
        for (auto num : nums)
            sum += num;
        long long l = 0, r = sum;
        while (l < r)
        {
            long long mid = (l + r) >> 1;
            if (check(nums, m, mid))
                r = mid;
            else
                l = mid + 1;
        }
        return int(l);
    }
};

方案二：dp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
    int splitArray(vector<int> &nums, int m)
    {
        int n = nums.size();
        vector<long long> sub(n + 1, 0);
        // dp[i][j]表示把前i个数分成j段，所能达到的段内和的最大值最小
        vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, LONG_LONG_MAX));
        for (int i = 1; i <= n; i++)
            sub[i] = sub[i - 1] + nums[i - 1];
        dp[0][0] = 0;
        // 分成了 [0,k]和[k+1,j]
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= min(i, m); j++)
                for (int k = 0; k < i; k++)
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]));
        return int(dp[n][m]);
    }
};

最后修改于 2020-07-25

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。