Leetcode 410. Split Array Largest Sum
程序员文章站
2022-06-17 18:24:37
...
dp[i][j] 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值
i的范围是[1, j]
计算dp[i][j]时,对于所有1<=k<=j-1:
最后一个分组为nums[k+1]…nums[j]时,此时各个子数组中最大值为max(sum(nums[k+1:j+1]), dp[i-1][k])
遍历k得到最小的dp[i][j]
最终返回 dp[m][n] 即可
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<vector<int>> dp(m + 1, vector<int>(n, INT_MAX));
dp[1][0] = nums[0];
for (int j = 1; j < n; ++j) {
dp[1][j] = dp[1][j - 1] + nums[j];
for (int i = 2; i <= m; ++i) {
// 分割成i-1份,最后一份为nums[k+1],...nums[j]
for (int k = 0; k < j; ++k) {
// sum_k = nums[k+1] + nums[k+2] + ... + nums[j]
int sum_k = dp[1][j] - dp[1][k];
dp[i][j] = min(dp[i][j], max(sum_k, dp[i - 1][k]));
}
}
}
return dp[m][n];
}
};
上一篇: 让群晖“文本编辑器”支持更多文件扩展名
下一篇: mvn 用法
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
Split Array Largest Sum 二分查找应用 C实现
-
2018 Bytedance AI Camp 编程题2: Split Array Largest Sum
-
410. Split Array Largest Sum
-
LeetCode 410. Split Array Largest Sum
-
Leetcode 410. Split Array Largest Sum
-
LeetCode 167 Two Sum II - Input array is sorted(左右指针)
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
Kth Largest Element in an Array Leetcode #215 题解[C++]
-
LeetCode 215 Kth Largest Element in an Array