474. 一和零

​

​

dp[i][w1][w2]:

• DP 数组的集合：考虑前i个物品包括第i个，满足背包重量不超过[w1][w2]的所有集合
  把输入数组中的每个string当作是一个物品，其重量分别为string中0和1的个数

• 属性：价值
  每个物品的价值是1因为我们求最大子集的个数，一个字符串对子集个数贡献的价值为1

• 状态转移方程：

  • ​

    

     

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]

        #遍历每个物品
        for i in range(1, len(strs)  + 1):
            # Count the number of 0s and 1s in the current string as weight
            w0 = strs[i - 1].count("0")
            w1 = strs[i - 1].count("1")
            #遍历所有重量的集合
            for w_0 in range(m + 1): 
                for w_1 in range(n + 1):
                    if w_0 >= w0 and w_1 >= w1:# make sure the bag is large enough
                        dp[i][w_0][w_1] = max(dp[i - 1][w_0][w_1], dp[i - 1][w_0 - w0][w_1 - w1] + 1 )
                    else:
                        dp[i][w_0][w_1] = dp[i - 1][w_0][w_1]
                
        return dp[len(strs)][m][n]

　　一刷错误：不能从 for w_0 in range(1，m + 1): 不然会少更新dp[i][0][1], dp[i][0][2]这些数组的

• 滚动数组优化

  • class Solution:
        def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
            dp = [[0] * (n + 1) for _ in range(m + 1)]
    
            #遍历每个物品
            for i in range(1, len(strs)  + 1):
                # Count the number of 0s and 1s in the current string as weight
                w0 = strs[i - 1].count("0")
                w1 = strs[i - 1].count("1")
                #遍历所有重量的集合
                for w_0 in range(m, w0 - 1,-1): # [include, include (parameter + 1), step]
                    for w_1 in range(n, w1 - 1, -1):
                        dp[w_0][w_1] = max(dp[w_0][w_1], dp[w_0 - w0][w_1 - w1] + 1 )
    
            return dp[m][n]