题解 | 一和零

题干解析

题设给予一个字符串数组strs，该数组中每个字符串只包含0，和1。要求我们找到一个strs的子集，子集中所有字符串的0与1字符数分别不超过m与n。求可找到的最大子集的势（子集中元素个数）。

算法思路

本题本质上可以看作有两项限制的0/1背包问题：

我们设定状态值dp[i][j][k]，考虑前i个字符串，表示0的个数为j，1的个数为k的子数组中元素的个数。由此我们能够得到状态转移方程如下：

其中dp[i-1][j][k]表示不选择第i个字符串的情况，dp[i-1][j-cnt_0][k-cnt_1] + 1是选择的情况，二者取大。

同时由于DP状态转移过程中，只涉及i与i-1，因此可以只使用一个二维数组解决问题，优化内存占用。

实现代码

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (auto &s : strs) {
            int cnt0 = count(s.begin(), s.end(), '0');
            int cnt1 = s.size() - cnt0;
            for (int j = m; j >= cnt0; --j) {
                for (int k = n; k >= cnt1; --k) {
                    dp[j][k] = max(dp[j][k], dp[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

复杂度分析

• 时间复杂度：，其中t表示strs数组元素个数，表示第i+1个字符串的长度
• 空间复杂度：