474. Ones and Zeroes - LeetCode

class Solution {
public:
    vector<pair<int, int>> freq;
    int max_idx;
    int dp[700][120][120];

    int sol(int idx, int m, int n) {
        if (idx == max_idx) return 0;

        if (dp[idx][m][n] != -1) return dp[idx][m][n];

        int ans = sol(idx+1, m, n);

        if (freq[idx].first <= m && freq[idx].second <= n) {
            ans = max(ans, 1 + sol(idx+1, m-freq[idx].first, n-freq[idx].second));
        }

        return dp[idx][m][n] = ans;

    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        max_idx = strs.size();
        memset(dp, -1, sizeof dp);

        for (auto s : strs) {
            int ones = 0;
            int zeros = 0;
            for (auto l : s) {
                if (l == '1') ones++;
                else zeros++;
            }
            freq.push_back(make_pair(zeros, ones));
        }
        return sol(0, m, n);
    }
};