474. Ones and Zeroes

Leetcode link

解题思路

这个题目也太难懂了吧🤯

题目要求我们求出一个字符串数组的最长子集，约束条件是最长子集的所有 0 的个数加起来不能超过 m；所有 1 的个数加起来不能超过 n（注意是所有子集合并计算）

很明显是一道动态规划的题目，我们还是需要一个二维数组 dp

数组 dp[i][j] 表示 i 个 0 与 j 个 1 的最长子集

那么状态转移方程是什么呢？我们考虑到有一个字符串的 0 的个数为 zeros，1 的个数为 ones，状态转移方程可以写成：

dp[i][j] = max(dp[i][j], dp[i - zeros, j - ones] + 1)

前面的 dp[i][j] 表示不选这个字符串的最长子集，后面表示选择这个字符串之后的最长子集，求其最大值

最后总结一下流程：

• 首先初始化二维数组 dp 的每一个元素为 0
• 再来遍历字符串数组 strs，计算每一个字符串的 zeros 跟 ones
• 接着对 zeros 跟 ones 遍历，更新 dp 数组
• 返回 dp[m][n]

C++

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(string str:strs) {
            int zeros = count(str.begin(), str.end(), '0');
            int ones = count(str.begin(), str.end(), '1');
            for(int i = m;i >= zeros;i--) {
                for(int j = n;j >= ones;j--) {
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

Javascript

var findMaxForm = function(strs, m, n) {
    // dp[i][j]: i 个 0，j 个 1 的时候最长子集
    let dp = new Array(m+1).fill(0).map(arr=>new Array(n+1).fill(0));
    for(let str of strs) {
        let zeros = (str.match(/0/g) || []).length;
        let ones = (str.match(/1/g) || []).length;
        for(let i = m;i >= zeros;i--) {
            for(let j = n;j >= ones;j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    return dp[m][n];
};