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
class Solution { public static int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; for (String str : strs) { int[] count = count(str); for (int i = m; i >= count[0]; i--) { for (int j = n; j >= count[1]; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1); } } } return dp[m][n]; } private static int[] count(String s) { int[] result = new int[2]; char[] array = s.toCharArray(); for (int i : array) { result[i - '0']++; } return result; } }
0/1背包问题。。。每个string的0和1记录下来,每个string可以选或者不选,背包容量是m个0和n个1,求这个背包最多能放多少个string
dp[ i ][ j ]意思是给了i个0,j个1,最多能放多少个string,答案就应该是dp[ m ][ n ]
下面的转移方程里面左边是不算这个string,右边是算,算前先把背包腾出位置(就是string减掉需要的0和1),还是不太清楚为什么从m和n往后递减算,但感觉就应该这样做。。
dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
https://leetcode.com/problems/ones-and-zeroes/discuss/95811/Java-Iterative-DP-Solution-O(mn)-Space
https://github.com/tianyicui/pack/blob/master/V2.pdf