LeetCode 474 一和零
🟡 中等
https://leetcode.cn/problems/ones-and-zeroes/description/
由递归转到动态规划。
class Solution {
public:
// int sel_not(vector<string>& strs, int index, int cap_m, int cap_n) {
// if (index == strs.size()) {
// return 0;
// }
// int one_nums = count(strs[index].begin(), strs[index].end(), '1');
// int zero_nums = strs[index].size() - one_nums;
// if (zero_nums <= cap_m && one_nums <= cap_n) {
// int sel =
// sel_not(strs, index + 1, cap_m - zero_nums, cap_n - one_nums);
// int not_sel = sel_not(strs, index + 1, cap_m, cap_n);
// return max(1 + sel, not_sel);
// } else {
// return sel_not(strs, index + 1, cap_m, cap_n);
// }
// }
int findMaxForm(vector<string>& strs, int m, int n) {
int dp[strs.size() + 1][m + 1][n + 1];
memset(dp, 0, sizeof dp);
for (int i = strs.size() - 1; i >= 0; i--) {
int one_nums = count(strs[i].begin(), strs[i].end(), '1');
int zero_nums = strs[i].size() - one_nums;
for (int mm = 0; mm <= m; mm++) {
for (int nn = 0; nn <= n; nn++) {
if (zero_nums <= mm && one_nums <= nn) {
int sel = dp[i + 1][mm - zero_nums][nn - one_nums];
int not_sel = dp[i + 1][mm][nn];
dp[i][mm][nn] = max(1 + sel, not_sel);
} else {
dp[i][mm][nn] = dp[i + 1][mm][nn];
}
}
}
}
// return sel_not(strs, 0, m, n);
return dp[0][m][n];
}
};
进一步优化空间，这里要注意m和n的遍历顺序，为了防止之前的变量污染，因此要倒序。
class Solution {
public:
// int sel_not(vector<string>& strs, int index, int cap_m, int cap_n) {
// if (index == strs.size()) {
// return 0;
// }
// int one_nums = count(strs[index].begin(), strs[index].end(), '1');
// int zero_nums = strs[index].size() - one_nums;
// if (zero_nums <= cap_m && one_nums <= cap_n) {
// int sel =
// sel_not(strs, index + 1, cap_m - zero_nums, cap_n - one_nums);
// int not_sel = sel_not(strs, index + 1, cap_m, cap_n);
// return max(1 + sel, not_sel);
// } else {
// return sel_not(strs, index + 1, cap_m, cap_n);
// }
// }
int findMaxForm(vector<string>& strs, int m, int n) {
int dp[m + 1][n + 1];
memset(dp, 0, sizeof dp);
for (int i = strs.size() - 1; i >= 0; i--) {
int one_nums = count(strs[i].begin(), strs[i].end(), '1');
int zero_nums = strs[i].size() - one_nums;
for (int mm = m; mm >= 0; mm--) {
for (int nn = n; nn >= 0; nn--) {
if (zero_nums <= mm && one_nums <= nn) {
int sel = dp[mm - zero_nums][nn - one_nums];
int not_sel = dp[mm][nn];
dp[mm][nn] = max(1 + sel, not_sel);
} else {
dp[mm][nn] = dp[mm][nn];
}
}
}
}
// return sel_not(strs, 0, m, n);
return dp[m][n];
}
};