Dynamic programming - 474. One and zero

1 Title Description

Here's an array of binary strings strs And two integers m and n .

Please find out and return to strs Length of the largest subset of , This subset most Yes m individual 0 and n individual 1 .

If x All of the elements of are also y The elements of , aggregate x Is a collection y Of A subset of .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/ones-and-zeroes

2 Title Example

Example 1：

Input ：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
Output ：4
explain ： At most 5 individual 0 and 3 individual 1 The largest subset of is {“10”,“0001”,“1”,“0”} , So the answer is 4 .
Other smaller subsets that satisfy the question include {“0001”,“1”} and {“10”,“1”,“0”} .{“111001”} Not satisfied with the question , Because it contains 4 individual 1 , Greater than n Value 3 .

Example 2：

Input ：strs = [“10”, “0”, “1”], m = 1, n = 1
Output ：2
explain ： The largest subset is {“0”, “1”} , So the answer is 2 .

3 Topic tips

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] Only by ‘0’ and ‘1’ form
1 <= m, n <= 100

4 Ideas

This problem is very similar to the classic knapsack problem , But there is only one capacity different from the classical knapsack problem , This problem has two capacities , That is... In the selected string subset 00 and 11 The maximum number of .

The classical knapsack problem can be solved by two-dimensional dynamic programming , The two dimensions are goods and capacity . This problem has two capacities , Therefore, it is necessary to use three-dimensional dynamic programming to solve , The three dimensions are string 、00 Capacity and 11 The capacity of .

Start the dynamic rule trilogy ：

1. determine dp Array （dp table） And the meaning of subscripts
   dp[i][j]： At most i individual 0 and j individual 1 Of strs The size of the largest subset of is dp[i][j].
2. Determine the recurrence formula
   dp[i][j] It can be from the previous strs Derived from the string in ,strs The string in the has zeroNum individual 0,oneNum individual 1.
   dp[i][j] It could be dp[i - zeroNum][j - oneNum] + 1.
   Then we go through the process of traversal , take dp[i][j] The maximum of .
   So the recurrence formula ：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
   Now you can recall 01 Recursive knapsack formula ：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   A comparison will show that , A string of zeroNum and oneNum Equivalent to the weight of the article （weight[i]）, The number of strings is equivalent to the value of the item （value[i]）.
   This is a typical 01 knapsack ！ It's just that the weight of an object has two dimensions .
3. dp How to initialize an array
   Because the value of an item is not negative , For the initial 0, Guarantee the time of recurrence dp[i][j] Not covered by initial values .
4. Determine the traversal order
   The object is strs The string in , The capacity of the backpack is in the description of the topic m and n.
5. Give an example to deduce dp Array

5 My answer

class Solution {
    
    public int findMaxForm(String[] strs, int m, int n) {
    
        //dp[i][j] Express i individual 0 and j individual 1 Maximum subset of 
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
    
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
    
                if (ch == '0') {
    
                    zeroNum++;
                } else {
    
                    oneNum++;
                }
            }
            // Reverse traversal 
            for (int i = m; i >= zeroNum; i--) {
    
                for (int j = n; j >= oneNum; j--) {
    
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}