class Solution(object):
def findMaxForm(self, strs, m, n):
"""
:type strs: List[str]
:type m: int
:type n: int
:rtype: int
"""
# 这个题是一个01背包问题,不一样的是,背包的容量是2维的,有m和n
# 确定dp
# dp[i][j][k],使用前i个字符串,最多有j个0和k个1的strs的最大子集的大小为dp[i][j][k]
# i为可以选择的字符串,0<=i<=len(nums),0<=j<=m 0<=k<=n
# 状态转移方程
# 1.当j<zeros or k<ones此时不能取字符串nums[i],dp[i][j][k]=dp[i-1][j][k]
# 2.j>=zeros and k>=ones,此时可以取字符串nums[i],也可以不取
# 不取:dp[i][j][k]=dp[i-1][j][k]
# 取:dp[i][j][k]=dp[i-1][j-zeros][k-ones]+1, +1代表选取当前字符串,子集大小+1
# 初始化
dp = [[[0]*(n+1) for _ in range(m+1)] for _ in range(len(strs)+1)]
# 先遍历元素
for i in range(1, len(strs)+1):
# 选取元素后,先计算元素中0和1的数量
str_ = strs[i-1]
zeros = str_.count('0')
ones = str_.count('1')
for j in range(m+1):
for k in range(n+1):
dp[i][j][k] = dp[i-1][j][k]
if j>=zeros and k>=ones:
dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-zeros][k-ones]+1)
return dp[-1][-1][-1]
class Solution(object):
def findMaxForm(self, strs, m, n):
"""
:type strs: List[str]
:type m: int
:type n: int
:rtype: int
"""
# 优化,滚动数组
dp = [[0]*(n+1) for _ in range(m+1)]
for str_ in strs:
zeros = str_.count('0')
ones = str_.count('1')
# 倒序遍历
for i in range(m, zeros-1, -1):
for j in range(n, ones-1, -1):
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
return dp[-1][-1]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)