Description

Submission

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        auto new_dp = dp;
        for(int k = 0; k < strs.size(); ++k) {
            int zeros = 0, ones = 0;
            for(auto ch: strs[k]) {
                if(ch == '1') ones++;
                else zeros++;
            }

            for(int i = zeros; i <= m; ++i) {
                for(int j = ones; j <= n; ++j) {
                    new_dp[i][j] = max(dp[i-zeros][j-ones] + 1, dp[i][j]);
                }
            }
            dp = new_dp;
        }
        return dp[m][n];
    }
};

// dp[i][j] = max(dp[i-zeros][dp[j-ones]] + 1, dp[i][j])