474

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int dp[m+1][n+1];
        memset(dp, 0, sizeof dp);

        // Knapsack DP.
        // Here to reduce space from 3d to 2d, we have the loops iterating in reverse order.
        for(auto s: strs){
            vector<int> count = countZeroesOnes(s);
            for(int zeroes=m; zeroes>=count[0]; zeroes--){
                for(int ones=n; ones>=count[1]; ones--){
                    dp[zeroes][ones] = max(1+dp[zeroes-count[0]][ones-count[1]], dp[zeroes][ones]);
                }
            }
        }
        return dp[m][n];
    }

    vector<int> countZeroesOnes(string s){
        vector<int> cnt(2,0);
        for(int i=0; i<s.length(); i++){
            if(s[i] == '0')
                cnt[0]++;
            else
                cnt[1]++;
        }
        return cnt;
    }

};