动态规划08--一和零

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

思路分析

做到这道题的时候没什么思路，因此想到回顾一下之前的有关于背包问题的相关知识点，重新整理一下思路。

对于本题的情况，想要求的是最大的子集，因此基本的方法是统计0和1的数量就可以了，目标是让零和一的数量“装满要求”。同时，本题容易被混淆为多重背包问题，注意，本题中的物品是strs中的字符，将一个字符同时装入两个背包。

下面开始动态规划五部曲：

1. 由于本题有两个背包，定义为二维数组，dp[i][j]的含义是对于0容量为i、1容量为j的情况字符串的最大数量。
2. 确定dp数组的迭代规律：判断遍历到的当前字符是否要添加，如果要添加，dp[i][j] = dp[i-当前字符串中0的数量][j-当前字符串中1的数量] + 1;如果当前字符不添加，dp[i][j] = dp[i][j]不变，然后在两者之间取较大的值。变成公式就是dp[i][j] = Max(dp[i][j], dp[i-cur(0)][j-cur(1)])。
3. 确定dp数组的初始化方法：最开始，将所有的都初始化成0就行。
4. 迭代顺序，外层循环遍历物品，本题中就是strs，内层循环遍历背包，本题就是m和n，需要注意的是本题中需要有两层的m和n循环遍历。
5. 带入数据验证。

代码部分

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历，也就是前面说的倒序遍历
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); //dp数组的迭代方式
                }
            }
        }
        return dp[m][n];
    }
};