Given an array nums
which consists of non-negative integers and an integer m
, you can split the array into m
non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m
subarrays.
Example 1:
Input: nums = [7,2,5,10,8], m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Example 2:
Input: nums = [1,2,3,4,5], m = 2 Output: 9
Example 3:
Input: nums = [1,4,4], m = 3 Output: 4
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
A:
首先,试图计算平均值,再每次尽量均分。
但这样, 会有一种情况
average = 100, m =
1,2,4,5,6 99,99, 10, 9 ,8 , 7, ..... 这样的情况,还是需要把两个99 分开。 那样左
这样结束后, 需要 左右挪动 每个位置, 这样就会互相影响。
因此,这个应该是行不通的。
-------》 考虑分而治之的思想 , 再考虑, m的情况,可以分为 a+b = m的两种情况,因此我们试着考虑DP 算法
首先我考虑的是2维的DP,就是对于index (a,b) inclusive, 可以分成的最小的情况。
但是由于 m == 14,000,因此可能空间太大了。
因此考虑1维的, 由此变成,每次取下最前面的一个(或者几个),然后再分后面的till the end of nums array。
由此,数组就变成了 n * m的了。
这个题目比普通DP 困难之处是:每次m 增加一个, 那么之前的所有的index 从 a 到 b, 都需要重新update. 而不是规定于某一个index状态转移方程不好写。那么我用 HashMap 来存储。那么,我们对于每一个从 [ a, b] ---> minSum with k subarray.再想一下,其实 a 永远都是0 的,所以,我们就可以有了DP 的方式。每行 从k = 1...m 然后每个DP[k][end] 的值是从 [0, end] 被分为k 个subarray的minSum
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
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<int> total = nums;
// get the total sum for m == 1 (per each ending index)
for(int i= 1; i<n;i++){
total[i] += total[i-1];
}
vector<int> DP = total;
// DP[i] stands for [0,i] the minSum of k_split subarray
for(int k = 2; k<=m; k++){
vector<int> newDP(n, INT_MAX);
for(int cur = k-1; cur < n; cur++){
for(int preLast = k-2; preLast<cur; preLast++){
int minSplitSum = DP[preLast];
int curLastSum = total[cur]-total[preLast];
newDP[cur] = min(newDP[cur], max( minSplitSum, curLastSum));
if(curLastSum<=minSplitSum){ // no need to shrink
break;
}
}
}
DP = newDP;
}
return DP[n-1];
}
};
这个题的改善是可以在line 15的for loop, 写成 binary search.
Error:
Line 18, 一开始糊涂, 写成了 min( , min () ) 哎,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 | class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<int> total = nums; // get the total sum for m == 1 (per each ending index) for(int i= 1; i<n;i++){ total[i] += total[i-1]; } vector<int> DP = total; // DP[i] stands for [0,i] the minSum of k_split subarray for(int k = 2; k<=m; k++){ vector<int> newDP(n, INT_MAX); for(int cur = k-1; cur < n; cur++){ for(int preLast = k-2; preLast<cur; preLast++){ int minSplitSum = DP[preLast]; int curLastSum = total[cur]-total[preLast]; newDP[cur] = min(newDP[cur], max( minSplitSum, curLastSum)); if(curLastSum<=minSplitSum){ // no need to shrink break; } } } DP = newDP; } return DP[n-1]; } }; |
No comments:
Post a Comment