1
class Solution {
2
 public:
3
  int dp[102][102][601];
4
  int countzero(string s) {
5
    int c = 0;
6
    for (int i = 0; i < s.size(); i++) {
7
      if (s[i] == '0') c++;
8
    }
9
    return c;
10
  }
11
  int solve(vector<string> &strs, int index, int m, int n, int ans) {
12
    if (index == strs.size()) {
13
      return ans;
14
      // return 0;
15
    }
16

17
    int c0 = countzero(strs[index]);
18
    int c1 = strs[index].size() - c0;
19

20
    if (dp[m][n][index] != -1) return dp[m][n][index];
21

22
    int a = INT_MIN, b = INT_MIN;
23

24
    if (m - c0 >= 0 && n - c1 >= 0) {
25
      // int c=ans;
26
      a = solve(strs, index + 1, m - c0, n - c1, ans + 1);
27
    }
28
    b = solve(strs, index + 1, m, n, ans);
29
    return dp[m][n][index] = max(a, b);
30
  }
31
  int findMaxForm(vector<string> &strs, int m, int n) {
32
    memset(dp, -1, sizeof(dp));
33

34
    return solve(strs, 0, m, n, 0);
35
  }
36
};