<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>

#2023/05/06
#dp -01 背包
'''
因为这道题有两个limit，所以可以用i,j分别表示一个limit,用dp[i][j]来表示，但是相当于还是用的一维dp
因为只存了上一行的Nums[i],没有把之前所有的Nums[i]存起来，所以在遍历m,n的时候还是应该倒序遍历
1. dp[i][j]，代表有i个0，j个1 的最大个数
2. 不用当前这个strs[i],那就是dp[i][j]上一行的，用就是dp[i-zerosnums][j-onenums]+1,取最大
3. dp[0][0]=0
4. 因为这道题有两个limit，所以可以用i,j分别表示一个limit,用dp[i][j]来表示，但是相当于还是用的一维dp
因为只存了上一行的Nums[i],没有把之前所有的Nums[i]存起来，所以在遍历m,n的时候还是应该倒序遍历
'''
# class Solution:
#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
#         dp=[[0 for i in range(n+1)] for j in range(m+1)]
#         for s in strs:
#             zero=0
#             one=0
#             for c in s:
#                 if c=="0":
#                     zero+=1
#                 else:
#                     one+=1
#             for i in range(m,-1,-1):
#                 for j in range(n,-1,-1):
#                     if i-zero>=0 and j-one>=0:
#                         dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1)
#         return dp[-1][-1]


#2023/09/01
'''
之前的题只有一个背包总重量的限制，这道题有两个限制，m,n. 所以其实是一个三维数组
但同样可以简化一维变成2维
dp[i][j]代表最多有i个0和j个1的最多个数的substr的个数
还是两种情况，用当前的这一个和不用当前的这一个
dp[i][j]=max(dp[i][j],dp[i-zerosnums][j-onenums]+1)
初始化
dp[0][0]=0
'''
# class Solution:
#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
#         dp=[[0]*(n+1) for i in range(m+1)]
#         for s in strs:
#             zeroNums=0
#             oneNums=0
#             for i in s:
#                 if i=="0":
#                     zeroNums+=1
#                 else:
#                     oneNums+=1
#             for i in reversed(range(m+1)):
#                 for j in reversed(range(n+1)):
#                     if i-zeroNums>=0 and j-oneNums>=0:
#                         dp[i][j]=max(dp[i][j],dp[i-zeroNums][j-oneNums]+1)
#         return dp[-1][-1]


#2024/04/29
'''
本题中strs数组里的元素是物品，m和n相当于是一个背包有两个维度
dp[i][j][k]用截止到strs[k]的字符串组成最多i个1,j个0的最大子集
dp[i][j][k]=max(dp[i][j][k-1],dp[i-currOne][j-currZero][k-1]+1)
k需要从1开始，但是不方便初始化，所以加一行
'''
# class Solution:
#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
#         length=len(strs)
#         dp=[[[0]*(length+1) for j in range(n+1)] for i in range(m+1)]
#         for i in range(m+1):
#             for j in range(n+1):
#                 for k in range(1,length+1):
#                     currZero=0
#                     currOne=0
#                     for c in strs[k-1]:
#                         if c=='0':
#                             currZero+=1
#                         else:
#                             currOne+=1
#                     if i-currZero>=0 and j-currOne>=0:
#                         dp[i][j][k]=max(dp[i][j][k-1],dp[i-currZero][j-currOne][k-1]+1)
#                     else:
#                         dp[i][j][k]=dp[i][j][k-1]
#         return dp[-1][-1][-1]

#2024/05/25
'''
m,n很像背包问题的限度。对于背包问题，通常的格式是考虑要或者不要当前当前的元素
m代表0的限制，n的代表的是1的限制
所以对于每一个元素考虑用或者不用，基于这个角度考虑状态转移方程式
因为当前有两个限制以及一个需要遍历的元素，所以dp考虑三维
dp[i][j][k]代表达到i和j的限制，以及截止到k能够找到的最大长度
那么如果用当前K: dp[i-currZero][j-currOne][k-1]+1
不用当前k: dp[i][j][k-1]
所以需要初始化dp[i][j][0],为了方便可以多加一个default idx element, dp[i][j][0]=0
dp[0][j][k],多加一行,0
dp[i][0][k],多加一行,0
'''
# class Solution:
#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
#         dp=[[[0]*(len(strs)+1) for j in range(n+1)] for i in range(m+1)]
#         for i in range(m+1):
#             for j in range(n+1):
#                 for k in range(1,len(strs)+1):
#                     currZero=0
#                     currOne=0
#                     for s in strs[k-1]:
#                         if s=="0":
#                             currZero+=1
#                         else:
#                             currOne+=1
#                     if i>=currZero and j>=currOne:
#                         dp[i][j][k]=max(dp[i][j][k-1],dp[i-currZero][j-currOne][k-1]+1)
#                     else:
#                         dp[i][j][k]=dp[i][j][k-1]
#         return dp[-1][-1][-1]


#2024/06/09
'''
背包问题，有两个限制还有一个数组，所以三维
dp[i][j][k]不超过i个0，j个1，截止到k能到的最大接近i个0和j个1能有的最多的个数
'''
# class Solution:
#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
#         dp=[[[0]*(len(strs)+1) for j in range(n+1)] for i in range(m+1)]
#         for i in range(m+1):
#             for j in range(n+1):
#                 for k in range(1,len(strs)+1):
#                     currZero=0
#                     currOne=0
#                     for s in strs[k-1]:
#                         if s=="0":
#                             currZero+=1
#                         else:
#                             currOne+=1
#                     if i>=currZero and j>=currOne:
#                         dp[i][j][k]=max(dp[i][j][k-1],dp[i-currZero][j-currOne][k-1]+1)
#                     else:
#                         dp[i][j][k]=dp[i][j][k-1]
#         return dp[-1][-1][-1]

#2024/09/13
'''
给了一些string的list, 从这个list里面找到一些string, 使得他们1的个数小于n, 0的个数小于1
对于每一个str都有取它和不取两种状态。两种状态下结果如何取决的它之前是什么样的，所以dp

dp[i][j][k]代表截止到i，最多j个0，k个1的个数

那么对于每一个i来说如果不取，dp[i-1][j][k], 取dp[i-1][j-0的个数][k-1的个数]
所以每一个strs[i]要去统计0和1的个数
'''
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp=[[[0]*(n+1) for i in range(m+1)] for j in range(len(strs)+1)]
        for i in range(1, len(strs)+1):
            for j in range(m+1):
                for k in range(n+1):
                    currZero=0
                    currOne=0
                    for s in strs[i-1]:
                        if s=="0":
                            currZero+=1
                        else:
                            currOne+=1
                    if  k>=currOne and j>=currZero:
                        dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-currZero][k-currOne]+1)
                    else:
                        dp[i][j][k]=dp[i-1][j][k]
        return dp[-1][-1][-1]
73268