This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.
The title
You are given a binary string array STRS and two integers M and n. Find and return the length of the largest subset of STRS that has at most m zeros and N ones. If all the members of x are also members of y, set x is a subset of set y.
Example 1: input: STRS = [” 10 “, “0001”, “111001”, “1”, “0”], m = 5, n = 3 output: 4: The largest subset with at most five zeros and three ones is {“10″,”0001″,”1″,”0”}, so the answer is 4. Other, but smaller, subsets that satisfy the question include {“0001″,”1”} and {“10″,”1″,”0”}. {“111001”} does not satisfy the problem because it contains four ones and is greater than the value 3 of n.
Example 2: Input: STRS = [“10”, “0”, “1”], m = 1, n = 1 Output: 2 Explanation: The largest subset is {“0”, “1”}, so the answer is 2.
Train of thought
This is also a typical backpack problem, the actual is the maximum number of items can be selected. Almost all backpack problems, can be found in “backpack nine” ideas, look at the document to do the backpack topic, there will be some ideas. Unlike ordinary backpacks, which only cost capacity, this problem is a two-dimensional backpack of 1 and 0, so when defining the state, it has to be one more dimension than ordinary backpacks. Define a 3d array dp. Dp [I][j][k] represents the maximum number of items that can be selected from the first I item of the string array when the cost of 0 and 1 is limited to J and K. For item I, if you don’t select it, then yes
dp[i][j][k] = dp[i-1][j][k]
If you choose, then yes
dp[i][j][k] = dp[i-1][j-num0i][k-num1i]
After finishing, the state escape equation can be obtained as:
dp[i][j][k] = dp[i-1][j][k]
dp[i][j][k] = dp[i-1][j-num0i][k-num1i] (j>=num01 && k >= num1i)
For the boundary condition, when I = 0, there are no elements in the string array to choose from, so dp[0][j][k] = 0.
Java version code
class Solution { public int findMaxForm(String[] strs, int m, int n) { int len = strs.length; int[][][] dp = new int[len+1][m+1][n+1]; for (int i = 1; i <= len; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= n; k++) { dp[i][j][k] = dp[i-1][j][k]; int num0 = 0, num1 = 0; for (int index = 0; index < strs[i-1].length(); index++) { if (strs[i-1].charAt(index) == '1') { num1++; } else { num0++; } } if (j >= num0 && k >= num1) { dp[i][j][k] = Integer.max(dp[i][j][k], dp[i-1][j-num0][k-num1] + 1); } } } } return dp[len][m][n]; }}Copy the code