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
0sand1swill 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 = 3Output: 4Explanation: 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 = 1Output: 2Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1". 题目含义：这道题的意思是给了m个0和n个1，还有一堆01构成的字符串，用这m个0和n个1最多能组成那堆字符串里的几个字符串。 这道题的基本思想也就是DP，其实就是顺序扫描字符串，每加入一个字符串，都用DP公式计算下 1 // 题目中给定m个0与n个1，dp[m][n]就标记了在当前的字符串序列下，能够用m个0与n个1取得的最多字符串。显然，dp[0][0] = 0 2 // ,因为没有0与1可用的时候，必然得不到字符串.dp[m][n] = max{dp[m][n],dp[m-m0][n-n0]+1},针对每一个字符串，实质上我们都采取两种策略， 3 // 选这个字符串，还是不选。做决定之前，先统计这个字符串(第i个)有多少个0与1，分别记为m0与n0，如果不选这个字符串， 4 // 那么dp[m][n]的值不会发生任何改变，但是选了之后，它的值就是用了m-m0个0 与n-n0个1，所得到的最多的字符串，也就是f[m-m0][n-n0]再加上1 5 int[][] dp = new int[m + 1][n + 1]; 6 for (String curr:strs) 7 { 8 int num0 = 0, num1 = 0; 9 for (int j = 0; j < curr.length(); j++) {10 if (curr.charAt(j) == '0') num0++;11 else num1++;12 }13 for (int i = m; i >= num0; i--) {14 for (int j = n; j >= num1; j--) {15 dp[i][j] = Math.max(dp[i][j], dp[i - num0][j - num1] + 1);16 }17 }18 }19 return dp[m][n];