目录
力扣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 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]仅由'0'和'1'组成1 <= m, n <= 100
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
}
};解析代码
先看能不能将问题转化成我们熟悉的题型。
在一些物品中挑选一些出来，然后在满足某个限定条件下，解决一些问题，大概率是背包模型， 由于每一个物品都只有 1 个，因此是一个01 背包问题。 但是发现这一道题里面有两个限制条件。因此是一个二维费用的 01 背包问题。那么定义状态表示的时候，创建一个三维 dp 表，把第二个限制条件加上即可。
二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（例：背包容量，问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。）
故：对于01背包问题、完全背包问题和多重背包问题的方法都完全可以使用，只不过增加一个代价。
状态表示：dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ，字符 1 的个数不超过 k ，所有的选法中，最大的长度。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。为了方便叙述，记第 i 个字符中，字符 0 的个数为 a ，字符 1 的个数为 b ：
- 不选第 i 个字符串：相当于就是去前 i - 1 个字符串中挑选，并且字符 0 的个数不超 过 j ，字符 1 的个数不超过 k 。此时的最大长度为 dp[i][j][k] = dp[i - 1] [j][k] 。
- 选择第 i 个字符串：那么接下来仅需在前 i - 1 个字符串里面，挑选出来字符 0 的 个数不超过 j - a ，字符 1 的个数不超过 k - b 的最长长度，然后在这个长度后面加 上字符串 i 即可。此时 dp[i][j][k] = dp[i - 1][j - a][k - b] + 1 。 但是这种状态不⼀定存在，因此需要特判⼀下。
综上，状态转移方程为：dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a] [k - b] + 1) ;
初始化： 每一维多开一个空间方便初始化，当 第一维i为0 即没有字符串的时候，没有长度，因此初始化为 0 即可。
填表顺序： 保证第一维i 从小到大即可。
返回值： 根据状态表示，返回 dp[len][m][n] ，其中 len 表示字符串数组的长度。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,
// 字符 1 的个数不超过 k ，所有的选法中，最大的长度
int len = strs.size();
vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
for(int i = 1; i <= len; ++i)
{
int a = 0, b = 0;
for(auto& e : strs[i - 1]) // 统计0和1的个数
{
if(e == '0')
++a;
else
++b;
}
for(int j = 0; j <= m; ++j)
{
for(int k = 0; k <= n; ++k)
{
if(j >= a && k >= b)
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + 1) ;
else
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
return dp[len][m][n];
}
};代码优化
所有的背包问题，都可以进行空间上的优化。 对于二维费用的 01 背包问题，优化还是和之前的01背包类似，删掉第一维，然后修改其他维度的遍历顺序：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,
// 字符 1 的个数不超过 k ，所有的选法中，最大的长度
int len = strs.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= len; ++i)
{
int a = 0, b = 0;
for(auto& e : strs[i - 1]) // 统计0和1的个数
{
if(e == '0')
++a;
else
++b;
}
for(int j = m; j >= 0; --j)
{
for(int k = n; k >= 0; --k)
{
if(j >= a && k >= b)
dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1) ;
else
dp[j][k] = dp[j][k];
}
}
}
return dp[m][n];
}
};
