首页 > 代码库 > 474. Ones and Zeroes
474. Ones and Zeroes
本周继续练习动态规划的相关题目。
题目:
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s
and n 1s
respectively. On the other hand, there is an array with strings consisting of only 0s
and 1s
.
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.
Note:
- The given numbers of
0s
and1s
will both not exceed100
- The size of given string array won‘t exceed
600.
示例:
Example 1:
Input: Array = {"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: Array = {"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".
题解:
同样地,这道题需要通过动态规划来解决,因为不能贪心地去换尽量短的字符,当两个字符长度相同的时候,用贪心算法无法决定选哪一个。
因此,这道题需要通过动态规划来解决。题目中给定m个0与n个1,dp[m][n]就标记了在当前的字符串序列下,能够用m个0与n个1取得的最多字符串。
显然,dp[0][0] = 0,因为没有0与1可用的时候,必然得不到字符串
dp[m][n] = max{dp[m][n],dp[m-m0][n-n0]+1}
针对每一个字符串,实质上我们都采取两种策略,选这个字符串,还是不选。做决定之前,先统计这个字符串(第i个)有多少个0与1,分别记为m0与n0,如果不选这个字符串,那么dp[m][n]的值不会发生任何改变,但是选了之后,它的值就是用了m-m0个0 与n-n0个1,所得到的最多的字符串,也就是f[m-m0][n-n0]再加上1,有点类似于经典0-1背包问题
代码:
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { // m个0 n个1 vector<vector<int> > dp(m+1,vector<int>(n+1,0)); for (int i = 0 ; i < strs.size();i++) { string curr = strs[i]; int num0 = 0,num1 = 0; for(int j = 0; j < curr.length();j++) { if(curr[j] == ‘0‘) num0++; if(curr[j] == ‘1‘) num1++; } for(int j = m; j >=num0; j--) { for(int i = n;i >= num1 ;i--) { dp[j][i] = max(dp[j][i],dp[j-num0][i-num1]+1); } } } return dp[m][n]; } };
474. Ones and Zeroes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。