Leetcode 474. 一和零 多重背包问题，动态规划

原题链接：Leetcode 474. 一和零

参考官解：Leetcode 474. 一和零

三维数组：

class Solution {
public:
    vector<int> sum01(string s) {
        int a = 0, b = 0;
        for (auto x : s) {
            if (x == '0')
                a++;
            else
                b++;
        }
        return {a, b};
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        int l = strs.size();
        // dp[i][j][k]表示使用前i个字符，最多有j个0，k个1的最大子集的长度
        int dp[l + 1][m + 1][n + 1];
        for (int i = 0; i <= l; i++) {
            int a = 0, b = 0;
            if (i > 0) {
                vector<int> tmp = sum01(strs[i - 1]);
                a = tmp[0];
                b = tmp[1];
            }
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (i == 0) {
                        dp[i][j][k] = 0;
                    } else {
                        if (j < a || k < b) {
                            dp[i][j][k] = dp[i - 1][j][k];
                        } else {
                            dp[i][j][k] = max(dp[i - 1][j - a][k - b] + 1,
                                              dp[i - 1][j][k]);
                        }
                    }
                }
            }
        }
        return dp[l][m][n];
    }
};

空间优化

class Solution {
public:
    vector<int> sum01(string s) {
        int a = 0, b = 0;
        for (auto x : s) {
            if (x == '0')
                a++;
            else
                b++;
        }
        return {a, b};
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        int l = strs.size();
        // dp[j][k]表示使用前i个字符，最多有j个0，k个1的最大子集的长度
        int dp[m + 1][n + 1];
        for (int i = 0; i <= l; i++) {
            int a = 0, b = 0;
            if (i > 0) {
                vector<int> tmp = sum01(strs[i - 1]);
                a = tmp[0];
                b = tmp[1];
            }
            for (int j = m; j >= a; j--) {
                for (int k = n; k >= b; k--) {
                    if (i == 0) {
                        dp[j][k] = 0;
                    } else {
                        dp[j][k] = max(dp[j - a][k - b] + 1, dp[j][k]);
                    }
                }
            }
        }
        return dp[m][n];
    }
};