今天继续学习动规解决01背包问题的最后一题——一和零

474.一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

思路：

1.有了前面几天的基础后，本题具体化为背包问题还是有一定想法了。strs是一个字符串数组，其中每一个字符串元素都可以看做是一个物品，但本题实际上需要的是字符中0和1的个数，因此还要统计单个字符串内的0和1的规格书；与此同时，背包也变成了一个二维的，因为我们要同时满足m个0和n个1。而本题最终要求的是装满这个背包的最大元素个数。

2.首先想dp数组的含义，dp[i][j]表示背包容量为i个0，j个1，装满这个背包的最大元素个数。

3.然后想递推公式，对于dp[i][j]，单个元素依旧是采取放或者不放。如果不放那么就是dp[i][j]，如果放，那么就是dp[i - x][j - y] + 1（其中x和y统计的是当前字符串内的0、1个数。至于为什么要加1，注意本题要求的是元素个数）。因此dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1)。

4.然后想初始化，当m和n均为0时，显然背包不需要物品就已经是装满状态了，因此dp[0][0]初始化为0，而其他元素因为递推公式涉及到取最大值，因此也都初始化为0即可。

5.最后是遍历顺序，依然是先遍历物品再遍历背包，且背包要后序遍历。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));//遍历物品for(string str : strs){int x = 0, y = 0;//记录单个字符串中0和1的个数for(char c : str){if(c == '0') x++;else y++;}//遍历背包for(int i = m; i >= x; i--){for(int j = n; j >= y; j--){dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp[m][n];}
};

启发：

1.本题相对于前面的01背包问题，首先依旧是弄清楚题目具体到底要求什么很重要（目前所做的几个01背包问题要求的东西实际各不相同）。

其次本题物品（从字符串数组到单个字符串再到单个字符）和背包（同时满足0和1的个数）实际上都是二维的，遍历时也都采取了二维的for循环。