C++刷LeetCode（474. 一和零）【动态规划】【0-1背包】

糖逗

题目描述：

1. 
   
2. 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
   
3. 
   
4. 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
   
5. 
   
6. 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
   
7. 
   
8. 
   
9. 
   
10. 示例 1：
    
11. 
    
12. 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
    
13. 输出：4
    
14. 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
    
15. 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
    
16. 示例 2：
    
17. 
    
18. 输入：strs = ["10", "0", "1"], m = 1, n = 1
    
19. 输出：2
    
20. 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
    
21. 
    
22. 
    
23. 提示：
    
24. 
    
25. 1 <= strs.length <= 600
    
26. 1 <= strs[i].length <= 100
    
27. strs[i] 仅由 '0' 和 '1' 组成
    
28. 1 <= m, n <= 100

复制代码

1. class Solution {
   
2. public:
   
3.     vector<int>count(string x){
   
4.         vector<int>res(2, 0);
   
5.         for(auto cha : x){
   
6.             res[cha - '0']++;
   
7.         }
   
8.         return res;
   
9.     }
   
10.     int findMaxForm(vector<string>& strs, int m, int n) {
    
11.         //0-1背包问题
    
12.         //这里的子集个数等价于能有多少个字符串被包含在内
    
13.         //dp[i][j][k]前i个元素中最多有j个0和n个1的子集个数
    
14.         int len = strs.size();
    
15.         vector<vector<vector<int> > >dp(len+1, vector<vector<int> >(m+1, vector<int>(n+1, 0)));
    
16.         for(int i = 1; i <= len; i++){
    
17.             //计算当前字符串中0和1的个数
    
18.             vector<int>store = count(strs[i-1]);
    
19.             for(int j = 0; j <= m; j++){
    
20.                 for(int k = 0; k <= n; k++){
    
21.                     if(store[0] > j || store[1] > k){
    
22.                         dp[i][j][k] = dp[i-1][j][k];
    
23.                     }else{
    
24.                         //装和不装两者选最大的
    
25.                         dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - store[0]][k - store[1]] + 1);
    
26.                     }
    
27. 
    
28.                 }
    
29.             }
    
30.         }
    
31.         return dp[len][m][n];
    
32.     }
    
33. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ti-labuladongdong-/