Leetcode 474: Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/description/

Notes:

This question actually is a typical knapsack problem. More specifically, there are two knapsacks: one is for 1s and the other is for 0s. So it is a 01 two-bags knapsack problem. More details can be found in this post.

See the code below:

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        vector<vector<int>> cts;
        for(auto &a : strs) {
            int n = a.size(), ct = 0;
            for(auto &b : a) {
                if(b == '1') ++ct;
            }
            cts.push_back({n-ct, ct});
        }
        for(int i=0; i<cts.size(); ++i) {
            for(int j=m; j>=cts[i][0]; --j) {
                for(int k=n; k>=cts[i][1]; --k) {
                    dp[j][k] = max(dp[j][k], dp[j-cts[i][0]][k-cts[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};