LeetCode 474 一和零

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

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

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

示例：

输入：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 。

动态规划

问题的要求：寻找数组的子集，在子集中最多包含 m 个 0 和 n 个 1 ，使得子集中的元素尽可能的多。

此处完全就是一个0/1背包问题，背包的容量为： m 个 0 和 n 个 1 ，每一个物品的价值都是1，要装下尽可能多的物品。将背包的维度从原本的一维情形转变成了2维。

动态规划数组的定义：定义数组 dp[m+1][n+1] ，其中 dp[i][j] 表示能装 i 个 0 、 j 个 1 的背包能够放下的物品个数。
动态规划数组的推导：在第 k 次迭代中，在 0-k 个元素中进行选择，相较于上一次迭代，新增了第 k 个元素，记第 k 个元素中 0 的个数为， 1 的个数为，此处有两种情况：可以选择元素 k ，或者不选元素 k ，应该在两者之中选择能够装下最多元素数量的情形，那么递推公式为：
$dp[i][j]=max(dp[i-k_0][j-k_1]+1,dp[i][j])$
动态规划数组的初始化：在初始状态仅在元素 0 中进行选择，那么对于 dp[m][n] 首先全初始化为 0 ，对与的
动态规划数组的遍历顺序：外层循环将元素逐个加入，从左向右遍历元素数组 strs ，内层循环遍历动态规划数组，并且为了防止重复选择 i,j 都需要从大到小进行遍历。

举例验证：对于 strs = ["10", "0", "1"], m = 1, n = 1 动态规划数组的求解过程为：验证正确。

dp[2][2]=[[0 0], [0 1]]

dp[2][2]=[[0 1], [0 1]] 

dp[2][2]=[[0 1], [1 2]]

代码实现：(在本题中，动态规划数组可以全部初始化为0，外层循环从第 0 个元素开始选取，下述代码实现中采用这样的方式)

class Solution {
public:
    void string2nums(string &s,int &n0,int &n1){
        for(auto a:s){
            if(a=='0') n0++;
            else n1++;
        }
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int k=0;k<strs.size();k++){
            int n0=0,n1=0;
            string2nums(strs[k],n0,n1);
            for(int i=dp.size()-1;i>=n0;i--){
                for(int j=dp[0].size()-1;j>=n1;j--){
                    dp[i][j]=max(dp[i-n0][j-n1]+1,dp[i][j]);
                }
            }
        }
        return dp.back().back();
    }
};

Mark's blogs

LeetCode-474-一和零

LeetCode 474 一和零

动态规划