## [474\. Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/)

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

:::spoiler 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` 代表的是加了這次的選擇
:::

:::spoiler 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)$
:::