动态规划1和0

1. 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
2. 解题思路：动态规划。
   1. 定义三维数组dp，其中dp[i][j][k] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量。假设数组 str 的长度为 l，则最终答案为 dp[l][m][n]。
   2. 当没有任何字符串可以使用时，可以得到的字符串数量只能是 0，因此动态规划的边界条件是：当 i=0 时，对任意 0≤j≤m 和 0≤k≤n，都有 dp[i][j][k]=0。
   3. 当 1≤i≤l 时，对于strs 中的第 i 个字符串（计数从 1 开始），首先遍历该字符串得到其中的 0 和 1 的数量，分别记为 zeros 和 ones，然后对于 0≤j≤m 和 0≤k≤n，计算 dp[i][j][k] 的值。
   4. 当 0 和 1 的容量分别是 j 和 k 时，考虑以下两种情况：
      1. 如果j<zeros 或 k<ones，则不能选第 i 个字符串，此时有dp[i][j][k]=dp[i−1][j][k]；
      2. 如果j≥zeros 且 k≥ones，则如果不选第 i 个字符串，有 dp[i][j][k]=dp[i−1][j][k]，如果选第 i 个字符串，有dp[i][j][k]=dp[i−1][j−zeros][k−ones]+1，dp[i][j][k] 的值应取上面两项中的最大值。

      3. class Solution:
             def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
                 dp=[[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs)+1)]
                 for i in range(1,len(strs)+1):
                     zeros=strs[i-1].count('0')
                     ones=strs[i-1].count('1')
                     for j in range(m+1):
                         for k in range(n+1):
                             dp[i][j][k]=dp[i-1][j][k]
                             if zeros<=j and ones<=k:
                                 dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeros][k-ones]+1)
                 return dp[-1][-1][-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes