Given an array, strs
, with strings consisting of only 0s
and 1s
. Also two integers m
and n
.
Now your task is to find the maximum number of strings that you can form with given m 0s
and n 1s
. Each 0
and 1
can be used at most once.
Example 1:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4 Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1 Output: 2 Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
Constraints:
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i]
consists only of digits '0' and '1'.1 <= m, n <= 100
A:
就是0/1 knapsack 问题。
本来一开始我觉得用3D array 做memorization . 太多了,不够。
就继续思考每次选最少0 或者 最少1 的。 结果不行(?????????为啥呢?)
最终,看了网上,每次增加一个 string. 并DP,
如果倒着计算,就可以直接利用之前的结果。
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> V; for(auto str : strs){ int c0 = 0, c1 = 0; for(auto ch : str){ if(ch == '0'){ c0++; }else{ c1++; } } V.push_back(vector<int>{c0,c1}); } // Now problem is to find longest subarray of V, S.t. V[i] to V[j] // initially, we might need a 3D vector, V.size(), m+1, n+1 . But then it turns out if we update backword, then former values are not updated yet. So, we can use 2D vector<vector<int>> M(m+1,vector<int>(n+1,0)); for(auto tmp : V){ int c0 = tmp[0], c1 = tmp[1]; for(int i = m; i>=0;i--){ for(int j = n; j>=0; j--){ if(i-c0 >= 0 and j -c1 >=0 ) M[i][j] = max(M[i][j], 1 + M[i-c0][j-c1]); else{ break; // early break Just to speed up } } } } return M[m][n]; } };
No comments:
Post a Comment