Keshawn_lu's Blog

Leetcode 410. 分割数组的最大值

动态规划 数组
字数统计: 597阅读时长: 2 min
2020/07/25 Share

题目简介：

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

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

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

思路：

动态规划，dp[i][j]代表前i个数字分成j段，所有情况下，其各段和的最大值中的最小值。

首先定义一个sub[i]，代表前i个数字的和。

对于dp[i][j]，我们可以定义一个k，将i个数分成1 ~ k和k + 1 ~ i，其中1 ~ k包括了前j - 1段，则第j段的数字便为k + 1 ~ i。

所以每次划分，得到的和的最大值为long sum = max(dp[k][j - 1], sub[i] - sub[k])，即前j - 1段的和的最大值的最小值与第j段的和进行比较。

最后dp[i][j]为这些最大值的最小值，即min(dp[i][j], sum)。

最后返回dp[nums.size()][m]即可。

tips:

  • 由于i个数字最多只能分成i段，所以j <= min(i, m)。(即m > nums.size()时返回0即可)。
  • 需要使用long来存储数组，否则会溢出。

代码如下：

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
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {

        //dp[i][j], 前i个数分成j段后的 和的最大值的 最小值
        vector<vector<long>> dp(nums.size() + 1, vector<long>(m + 1, INT_MAX));
        //sub[i], 前i个数的和
        vector<long> sub(nums.size() + 1, 0);

        sub[1] = nums[0];
        for(int i = 2; i <= nums.size(); i++){

            sub[i] = sub[i - 1] + nums[i - 1];
        }

        dp[0][0] = 0;
        for(int i = 1; i <= nums.size(); i++){

            for(int j = 1; j <= min(i, m); j++){

                //前k个数分成了j - 1段,  k + 1 ~ i 为第j段
                for(int k = 0; k < i; k++){

                //第j - 1段的 和的最大值的 最小值 与第j段的和进行比较, 得出最大值
                    long sum = max(dp[k][j - 1], sub[i] - sub[k]);
                    dp[i][j] = min(dp[i][j], sum);
                }
            }
        }

        return dp[nums.size()][m];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网