LeetCode Weekly Contest 12

Leetcode_474_Ones_and_Zeroes.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct node {
    int z, o;

    node() {}

    node(int z, int o) : z(z), o(o) {}
};
class Solution {
public:
    //二维费用背包
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        vector<node> cost;
        for (auto str : strs) {
            int z = 0, o = 0;
            for (auto ch : str) {
                if (ch == '0') {
                    ++z;
                } else if (ch == '1') {
                    ++o;
                }
            }
            cost.push_back(node(z, o));
        }
        for (int i = 0; i < cost.size(); ++i) {
            for (int j = m; j > 0; --j) {
                for (int k = n; k > 0; --k) {
                    if (cost[i].z <= j && cost[i].o <= k) {
                        dp[j][k] = max(dp[j - cost[i].z][k - cost[i].o] + 1, dp[j][k]);
                    }
                }
            }
        }
        return dp[m][n];
    }
};