leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题

亦凉 2022-06-02 23:22 59阅读 0赞

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 and 1s will both not exceed 100  
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”.

这道题其实很简单，怎么最初的时候想不起来怎么做呢，本题就是一个背包问题的改版，看来需要学习和进步的地方实在是太多了，差距还很大啊

还有 [leetcode 494. Target Sum目标和 + 背包问题 + 深度优先遍历DFS + 动态规划DP + 简单的分析推导 ][leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]

还建议和[leetcode 518. Coin Change 2 动态规划DP][leetcode 518. Coin Change 2 _DP]、[leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决][leetcode 279. Perfect Squares _ _ _DP] 、[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]和[leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS][leetcode 416. Partition Equal Subset Sum _DP _ _DFS]一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) 
        {
            //dp[i][j]表示有i个0和j个1可以装下的字符串的数量
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));
            for (string s : strs)
            {
                int numOne = 0, numZero = 0;
                for (char c : s)
                {
                    if (c == '0')
                        numZero++;
                    else if (c == '1')
                        numOne++;
                }
    
                for (int i = m; i >= numZero; i--)
                {
                    for (int j = n; j >= numOne; j--)
                    {
                        dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1);
                    }
                }
    
            }
            return dp[m][n];
        }
    };

[leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]: http://blog.csdn.net/jackzhang_123/article/details/78793365
[leetcode 518. Coin Change 2 _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 279. Perfect Squares _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78117843
[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 416. Partition Equal Subset Sum _DP _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78752598