474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]仅由'0'和'1'组成1 <= m, n <= 100
思路
首先，这是一个二维0-1背包问题，可以使用三维数组解决。
f[i][j][k]:i代表0~i的选取结果,j代表不超过j个零,k同理。
f[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−当前字符串使用0的个数][k−当前字符串使用1的个数]+1)
dp[i−1][j][k] 不选择当前考虑的字符串i
dp[i−1][j−当前字符串使用0的个数][k−当前字符串使用1的个数]+1 选择当前考虑的字符串
初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。
点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
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 x1 = cnum(strs[i - 1]);
int x0 = strs[i - 1].size() - x1;
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (j >= x0 && k >= x1) {
dp[i][j][k] =
max(dp[i - 1][j][k], dp[i - 1][j - x0][k - x1] + 1);
}
}
}
}
return dp[len][m][n];
}
int cnum(string s) {
int cnt = 0;
for (auto c : s) {
if (c == '1')
cnt++;
}
return cnt;
}
};
参考
