感觉用图描述算法更直观,所以模仿y总,用画图描述算法 (说的不好的,喷轻点)
题目描述
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
样例
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
算法
(动态规划) $O(n^2*m)$
C++ 代码
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size() ;
vector<vector<long long>> f(n+1,vector<long long>(m+1,INT_MAX)) ;
vector<long long> s(n+1,0) ;//前缀和,便于求数组的区间和,因为爆int,取long long
f[0][0] = 0 ;
for(int i=0;i<n;i++){
s[i+1] = s[i] + nums[i] ;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<i;k++){
f[i][j] = min(f[i][j],max(f[k][j-1],s[i]-s[k])) ;
}
}
}
return f[n][m] ;
}
};
老哥稳!
拜学神,棒棒哒。
学渣路过。
棒棒