动态规划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

发表评论

电子邮件地址不会被公开。 必填项已用*标注