<p>You are given an array of binary strings <code>strs</code> and two integers <code>m</code> and <code>n</code>.</p>

<p>Return <em>the size of the largest subset of <code>strs</code> such that there are <strong>at most</strong> </em><code>m</code><em> </em><code>0</code><em>&#39;s and </em><code>n</code><em> </em><code>1</code><em>&#39;s in the subset</em>.</p>

<p>A set <code>x</code> is a <strong>subset</strong> of a set <code>y</code> if all elements of <code>x</code> are also elements of <code>y</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;10&quot;,&quot;0001&quot;,&quot;111001&quot;,&quot;1&quot;,&quot;0&quot;], m = 5, n = 3
<strong>Output:</strong> 4
<strong>Explanation:</strong> The largest subset with at most 5 0&#39;s and 3 1&#39;s is {&quot;10&quot;, &quot;0001&quot;, &quot;1&quot;, &quot;0&quot;}, so the answer is 4.
Other valid but smaller subsets include {&quot;0001&quot;, &quot;1&quot;} and {&quot;10&quot;, &quot;1&quot;, &quot;0&quot;}.
{&quot;111001&quot;} is an invalid subset because it contains 4 1&#39;s, greater than the maximum of 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;10&quot;,&quot;0&quot;,&quot;1&quot;], m = 1, n = 1
<strong>Output:</strong> 2
<b>Explanation:</b> The largest subset is {&quot;0&quot;, &quot;1&quot;}, so the answer is 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strs.length &lt;= 600</code></li>
	<li><code>1 &lt;= strs[i].length &lt;= 100</code></li>
	<li><code>strs[i]</code> consists only of digits <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
</ul>

class Solution {
public:
    int si = 0;
    int cnt0(string s) {
        int cnt = 0;
        for (auto it : s) {
            if (it == '0')
                cnt++;
        }
        return cnt;
    }
    int helper(vector<string>& strs, int i, int m, int n,vector<vector<vector<int>>>&dp) {
        if (i == 0) {
            string s = strs[i];
            int zeroes = cnt0(s);
            int ones = s.size() - zeroes;
            if (zeroes <= m && ones <= n) {
                return 1;
            } else {
                return 0;
            }
        }
        if (m == 0 && n == 0)
            return 0;
        if(dp[i][m][n]!=-1)return dp[i][m][n];
        int include = -1;
        int notinclude = helper(strs, i - 1, m, n,dp);
        string s = strs[i];
        int zeroes = cnt0(s);
        int ones = s.size() - zeroes;
        if (zeroes <= m && ones <= n) {
            include = 1 + helper(strs, i - 1, m - zeroes, n - ones,dp);
        }
        return dp[i][m][n] = max(include, notinclude);
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        si = strs.size();
        vector<vector<vector<int>>>dp(si,vector<vector<int>>(m+1,vector<int>(n+1,-1)));
        // vector<int> mvalue(si + 1, 0);
        // vector<int> nvalue(si + 1, 0);
        // vector<int> dp(si + 1, 0);
        // mvalue[0] = m;
        // nvalue[0] = n;
        // int ans = 0;

        // for (int i = 1; i <= si; i++) {

        //     string s = strs[i - 1];

        //     int zeroes = cnt0(s);
        //     int ones = s.size() - zeroes;
        //     for (int j = 0; j < i; j++) {
        //         if (zeroes <= mvalue[j] && ones <= nvalue[j]) {
        //             if (dp[i] <= dp[j]) {
        //                 dp[i] = dp[j] + 1;
        //                 mvalue[i] = mvalue[j] - zeroes;
        //                 nvalue[i] = nvalue[j] - ones;
        //             } else {
        //             }
        //         }
        //     }
        //     ans = max(ans, dp[i]);
        // }
        return helper(strs,si-1,m,n,dp);
    }
};
108569