# 474. Ones and Zeroes (DP)

https://leetcode.com/problems/ones-and-zeroes/
You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.


靜下來思考一下哪些資訊可以用在DP上。很顯然這題要在讀str的時候判斷之前存取的哪個資訊可以運用。

以Example1為例:
第1個str是"10"，有1個'0'跟1個'1'，如果我希望在最多接受5個'0'跟3個'1'的情況下這個str"10"一定可以讓我的答案+1，那我就只要知道
`5-1=4(1個'0')`個'0'跟`3-1=2(1個'1')`個'1'時的答案再+1就好。而這個需要的答案又可以再往前取
。
所以我們會發現，我們需要儲存當m是0 ~ 5和n是0 ~ 3的答案，因此可以建一個table是6 * 4的矩陣來存。
所以經過第1個str後，table[1:, 1:]的答案全都變1，因為只要m>=1和n>=1都可以接受"10"這個str。

再來的str是"0001"，有3個'0'跟1個'1'，用一樣的邏輯下去做，我想知道m=5, n=3的答案，就需要table[m-3][n-1]的答案+1，因為如果我知道m=2, n=2的答案，我就知道m=5，n=3是肯定可以被接受的(差距剛好就是這個str，3個'0'跟1個'1')。所以走完這輪，table[2:, 2:]都是2，table[1:3][1:3]都是1。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> table(m+1, vector<int>(n+1, 0));
        for (auto str : strs) {
            int num_zero = 0, num_one = 0;
            for (auto s : str) {
                if (s == '1')
                    num_one++;
            }
            num_zero = str.size() - num_one;
            
            for (int i = m; i >= num_zero; i--) {
                for (int j = n; j >= num_one; j--) {
                    table[i][j] = max(table[i][j], table[i-num_zero][j-num_one] + 1);
                }
            }
        }
        return table[m][n];
    }
};