012动态规划

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 <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

---

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 定义二维dp数组：dp[i][j] 表示最多使用 i 个 0、j 个 1 时能选的最大字符串数量vector<vector<int>> dp(m+1, vector<int>(n+1, 0));// 遍历每一个字符串（相当于 01背包 中的每件物品）for(auto str : strs) {// 统计当前字符串中 0 的数量 x，1 的数量 yint x = 0;int y = 0;for(auto val : str) {if(val == '0') {x++;  // 统计 0 的个数} else {y++;  // 统计 1 的个数}}// 二维 01 背包逆序遍历，防止重复选取当前字符串for(int i = m; i >= x; i--) {for(int j = n; j >= y; j--) {// 状态转移方程：// 不选当前字符串 → 保持 dp[i][j]// 选当前字符串 → dp[i - x][j - y] + 1（+1 表示当前字符串）dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);}}}// 最终答案：最多使用 m 个 0、n 个 1 能选择的最大数量return dp[m][n];}
};

---

• dp[i] [j] ：背包容量能装i个0和j个1，最多可以背dp[i] [j] 个物品（物品的数量即为价值）

• dp[i] [j] = max(dp[i-x] [j-y]+1,dp[i] [j])

• Init: dp[0] [0] = 0

  只能装0个0和1，最多只能背0个物品

  其余的也全部初始化为0，防止影响最大值max的取值

• 先遍历物品，在遍历背包容量（有i和j两个维度，先后顺序无所谓）