-
hard:https://leetcode.cn/problems/split-array-largest-sum/
-
给定一个非负整数数组 nums 和一个整数 m ,
你需要将这个数组分成 m 个非空的连续子数组
。 -
设计一个算法使得这
m 个子数组各自和
的最大值最小
。
示例 1:
输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:
输入:nums = [1,2,3,4,5], m = 2
输出:9
示例 3:
输入:nums = [1,4,4], m = 3
输出:4
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
题解
-
令 dp[i][j]表示将数组的
前 i 个数分割为 j 组
所能得到的最大连续子数组和的最小值 -
确定装填转移方程(考虑dp[i][j]需要遍历所有分为j-1组的情况):
d p [ i ] [ j ] = m i n k = 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u b ( k + 1 , i ) ) } = m i n k = 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u m ( n u m s [ k + 1 … j ] ) ) } dp[i][j]= min_{k=0}^{ i−1} \{max(dp[k][j−1],sub(k+1,i))\}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = min_{k=0}^{ i−1} \{max(dp[k][j−1],sum(nums[k+1…j]))\} dp[i][j]=mink=0i−1{max(dp[k][j−1],sub(k+1,i))} =mink=0i−1{max(dp[k][j−1],sum(nums[k+1…j]))} -
确定边界:填表法文章来源:https://www.toymoban.com/news/detail-637212.html
nums = [7,2,5,10,8],m=2。文章来源地址https://www.toymoban.com/news/detail-637212.html
i\j | 0 | 1 | 2 |
---|---|---|---|
0 | 无法分为0组 | INT_MAX | INT_MAX |
1 | 无法分为0组 | 7 | 1个数无法分为2组(i<j) |
2 | 无法分为0组 | 7+2 | m i n ( [ 7 ] , [ 2 ] ) = 2 min([7],[2])=2 min([7],[2])=2 |
3 | 无法分为0组 | 7+2+5 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 ] ) ] = 7 min\begin{bmatrix} max(dp[1][1],[2,5]) \\ max(dp[2][1],[5]) \end{bmatrix}=7 min[max(dp[1][1],[2,5])max(dp[2][1],[5])]=7 |
4 | 无法分为0组 | 7+2+5+10 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 ] ) ] = 14 min\begin{bmatrix} max(dp[1][1],[2,5,10]) \\ max(dp[2][1],[5,10]) \\ max(dp[3][1],[10]) \end{bmatrix}=14 min max(dp[1][1],[2,5,10])max(dp[2][1],[5,10])max(dp[3][1],[10]) =14 前*个数分为一组和剩下的部分 |
5 | 无法分为0组 | 7+2+5+10+8 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 , 8 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 , 8 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 , 8 ] ) m a x ( d p [ 4 ] [ 1 ] , [ 8 ] ) ] = 18 min\begin{bmatrix} max(dp[1][1],[2,5,10,8]) \\ max(dp[2][1],[5,10,8]) \\ max(dp[3][1],[10,8])\\ max(dp[4][1],[8]) \end{bmatrix}=18 min max(dp[1][1],[2,5,10,8])max(dp[2][1],[5,10,8])max(dp[3][1],[10,8])max(dp[4][1],[8]) =18 |
code
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, LLONG_MAX));
vector<long long> sub(n + 1, 0);
for (int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + nums[i];
}
dp[0][0] = 0;
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];
}
};
到了这里,关于leetcode410. 分割数组的最大值 动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!