474. 一和零

思路

相當於01背包問題，不過現在的限制不只一個，而是有兩個，一個背包放0，一個放1。 第一個方法是記憶化搜索，透過遞迴把問題拆分成更小規模的子問題。

假設 cnt1[i] 代表 strs[i] 中有多少 1，cnt0[i] 代表 strs[i] 中有多少0。

dfs[i][j][k]代表strs的前i個物品中，在0至多放j個，1至多放k個的情況下，最多能放下幾個物品。

要想知道dfs[i][j][k]，需要考慮兩種情況

程式碼

1. 記憶化搜索

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> cnt0(strs.size());
        for(int i = 0; i < strs.size(); ++i) {
            cnt0[i] = ranges::count(strs[i], '0');
        }
        // memo[k][m][n] = 前 k 個字串, strs的最大子集長度, 最多有 m 個 0 跟 n 個 1
        vector memo(strs.size(), vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) {
            if(i < 0) {
                return 0;
            }
            int& res = memo[i][j][k];
            if(res != -1) {
                return res;
            }
            res = dfs(i - 1, j, k); // 不選
            int cnt1 = strs[i].size() - cnt0[i];
            if(j >= cnt0[i] && k >= cnt1) { // 選
                res = max(res, 1 + dfs(i - 1, j - cnt0[i], k - cnt1));
            }
            return res;
        };
        return dfs(strs.size() - 1, m, n);
    }
};

2.動態規劃

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(auto str : strs) {
            int i_min = ranges::count(str, '0');
            int j_min = str.size() - i_min;
            for(int i = m; i >= i_min; --i) {
                for(int j = n; j >= j_min; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - i_min][j - j_min] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

複雜度分析

• 時間複雜度：$O(mnk + L)$，$L$ 是 strs 中所有字串的長度和
• 空間複雜度：方法一$O(mnk)$，方法二$O(mn)$