这题感觉有点傻逼…难以理解
Leetcode Link: 474. 一和零 - 力扣（LeetCode）
题目
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
解法一
我的思路：从暴力递归到动态规划
- 暴力递归
子问题是到第 idx 位，我选还是不选。
这道题傻逼在，base case 就一个 idx==len(strs), 而没有 rest0==0 and rest1 == 0…
要想清楚为啥有效时候返回的是 0
实际上每个函数返回的结果是从当前位置到最后的位置上最大的子集个数 当 pick 一个子集的时候，结果+1，显然，当判定到”有效”时，没 pick 子集，所以返回的是 0，在上一层选择那个子集的时候 +1 可以用两个试试体会一下
学会子函数怎么返回 “个数”
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
res = self.process(strs, 0, m, n)
return res
def process(self, strs, idx, rest0, rest1):
if rest0 < 0 or rest1 < 0:
return -1 # 失效
if idx == len(strs) :
return 0 # 有效（先判定失效在判定有效）
# 情况1：pick 该位
p1 = self.process(strs, idx+1, rest0, rest1)
# 情况2：不 pick 该位， 注意提前判定有效性
p2 = -1
sum0 = strs[idx].count('0')
sum1 = strs[idx].count('1')
nnext = self.process(strs, idx+1, rest0-sum0, rest1-sum1)
if nnext != -1: # 有效性判定
p2 = nnext + 1
return max(p1, p2)
改写成动态规划，显然是个三维的
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# [idx, rest0, rest1]
dp = [[[-1 for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs)+1)]
for i in range(m+1):
for j in range(n+1):
dp[len(strs)][i][j] = 0
for i in range(len(strs)-1, -1, -1):
for j in range(m+1):
for k in range(n+1):
sum0 = strs[i].count('0')
sum1 = strs[i]. count ('1')
# 这里的越界判定不能写成 not (A or B)
if (not 0<=j-sum0< m+1) or (not 0<=k-sum1< n+1):
dp[i][j][k] = dp[i+1][j][k]
else:
dp[i][j][k] = max(dp[i+1][j-sum0][k-sum1]+1, dp[i+1][j][k])
return dp[0][m][n]题解：
解法二
思路： 代码随想录里能弄成二维的。
题解：
解法三
思路：
题解：