【leetcode题解-动态规划之0-1背包】474. 一和零（python版本+详细表格计算）

474. 一和零

本题为0-1背包，因为物品（strs中每一个字符串）只能使用一次，但是背包有两个：m，n分别表示最多装m个0和n个1的两个背包

即：weight维度为2（对应0，1的个数），每个字符串value为1，背包分别为容量为m和n的0背包和1背包

dp五部曲：

1. dp[i][j]:最多有i个0和j个1的字符串数组最大子集长度

2. 递推公式：dp[i][j]=max(dp[i][j],dp[i-sum0][j-sum1]+1)

sum0,sum1:当前字符串k所包含的0，1个数

dp[i][j]:不选择字符串k，则从0～k中进行选择的结果等于从0～k-1中选择的dp[i][j]

dp[i][j]:选择字符串k，则从0～k中进行选择的结果等于从0～k-1中选择的dp[i-sum0][j-sum1]（dp两个维度都减去当前字符串k的0，1个数）+1（当前字符串）

3. 初始化

dp全部初始化为0

4. 遍历方向

从右下角开始，从右到左，从下到上（保证不覆盖）

5. 举例推导

以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例

k=0

strs[k]="10" sum0=1 sum1=1

重点：从右下角开始，从右到左，从下到上（保证不覆盖）

dp	j=0	j=1	j=2	j=3
i=0	0	0	0	0
i=1	0	1	1	1
i=2	0	1	1	1
i=3	0	1	1	1

k=1

strs[k]="0001" sum0=3 sum1=1

dp	j=0	j=1	j=2	j=3
i=0	0	0	0	0
i=1	0	1	1	1
i=2	0	1	1	1
i=3	0	1	1	1

k=2

strs[k]="111001" sum0=2 sum1=4

dp	j=0	j=1	j=2	j=3
i=0	0	0	0	0
i=1	0	1	1	1
i=2	0	1	1	1
i=3	0	1	1	1

k=3

strs[k]="1" sum0=0 sum1=1

dp	j=0	j=1	j=2	j=3
i=0	0	1	1	1
i=1	0	1	2	2
i=2	0	1	2	2
i=3	0	1	2	2

k=4

strs[k]="0" sum0=1 sum1=0

dp	j=0	j=1	j=2	j=3
i=0	0	1	1	1
i=1	1	2	2	2
i=2	1	2	3	3
i=3	1	2	3	3

最终得到dp[3][3]=3为所求

python代码：

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        lens=len(strs)
        dp=[[0]*(n+1) for _ in range(m+1)]
        for s in strs:
            sum0=s.count('0')
            sum1=s.count('1')
            for i in range(m,sum0-1,-1):
                for j in range(n,sum1-1,-1):
                    dp[i][j]=max(dp[i][j],dp[i-sum0][j-sum1]+1)
        return dp[m][n]