[数据结构与算法]动态规划 背包问题 474. Ones and Zeroes (Medium)

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));
        for(int i = 1; i <= len; i++){
            auto [one,zero] = count(strs[i-1]);
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j >= zero && k >= one){
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one] + 1);
                    }
                    else
                        dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[len][m][n];
    }
    pair<int,int> count(string s){
        int one = 0, zero = 0;
        for(char c : s){
            if(c == '1')
                ++one;
            if(c == '0')
                ++zero;
        }
        return {one,zero};
    }
};