| 1 | class Solution: |
| 2 | def findMaxForm(self, strs: List[str], M: int, N: int) -> int: |
| 3 | # Dynamic Programming |
| 4 | dp = defaultdict(int) |
| 5 | |
| 6 | for s in strs: |
| 7 | mCnt, nCnt = s.count("0"), s.count("1") |
| 8 | for m in range(M, mCnt - 1, -1): |
| 9 | for n in range(N, nCnt - 1, -1): |
| 10 | dp[(m, n)] = max( |
| 11 | 1 + dp[(m - mCnt, n - nCnt)], |
| 12 | dp[(m, n)]) |
| 13 | return dp[(M, N)] |
| 14 | |
| 15 | # Memoization |
| 16 | dp = {} |
| 17 | |
| 18 | def dfs(i, m, n): |
| 19 | if i == len(strs): |
| 20 | return 0 |
| 21 | if (i, m, n) in dp: |
| 22 | return dp[(i, m, n)] |
| 23 | |
| 24 | mCnt, nCnt = strs[i].count("0"), strs[i].count("1") |
| 25 | dp[(i, m, n)] = dfs(i + 1, m, n) |
| 26 | if mCnt <= m and nCnt <= n: |
| 27 | dp[(i, m, n)] = max( |
| 28 | dp[(i, m, n)], |
| 29 | 1 + dfs(i + 1, m - mCnt, n - nCnt)) |
| 30 | return dp[(i, m, n)] |
| 31 | |
| 32 | return dfs(0, m, n) |