474. Ones and Zeroes

0/1 背包問題，對於每個 subset，有取或不取兩個選擇。

Hint

2 維的

$(m+1)\cdot (n+1)$ DP 陣列

對於每個狀態都有選，或不選兩個選擇

• 不選：dp[i][j]
• 選：dp[i - zeros][j - ones] + 1

狀態轉移：dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);

每個格子都是取最大的 subsets 的狀態

+ 1 代表的是加了這次的選擇

Solution

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

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (auto s : strs)
        {
            int zeros = 0, ones = 0;
            for (auto c : s) {
                c == '0' ? ++zeros : ++ones;
            }

            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];
    }
};

• 時間複雜度：
  $O(L\cdot M\cdot N)$
• 空間複雜度：
  $O(M\cdot N)$