思路:0-1背包问题 (滚动数组后,从右向左更新)
跟背包问题最大的区别是:这道题有两个限制,0-1背包是一个限制 dp[i][j][k]表示在0限制为j 1限制为k,前i个最大子集的个数。 转移方程:dp[i][j][k]=max(dp[i][j-a][k-b]+1,dp[i-1][j][k]) 边界全是0。
class Solution {
public:
pair<int, int> get(const string& s) {
int a = 0, b = 0;
for (auto& ch : s) {
if (ch == '0') a++;
else b++;
}
return {a, b};
}
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i < len; ++i) {
auto tmp = get(strs[i]);
int a = tmp.first, b = tmp.second;
for (int j = m; j >= a; --j) {
for (int k = n; k >= b; --k) {
dp[j][k] = max(dp[j - a][k - b] + 1, dp[j][k]);
}
}
}
return dp[m][n];
}
};
难点:三维分别为 len+1 m+1 n+1的数组怎么创建?
vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n+1)));
|