528
个编辑
更改
跳到导航
跳到搜索
第30行：
第30行： − {{TODO|添加代码}}+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→相关题目
=== 0-1 背包：[https://leetcode.com/problems/ones-and-zeroes LeetCode 474. Ones and Zeroes] ===
=== 0-1 背包：[https://leetcode.com/problems/ones-and-zeroes LeetCode 474. Ones and Zeroes] ===
<syntaxhighlight lang=python>
def count01(s: str) -> (int, int):
# ...
return (c0, c1)
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 s in strs:
c0, c1 = count01(s)
for n0 in reversed(range(c0, m + 1)):
for n1 in reversed(range(c1, n + 1)):
dp[n0][n1] = max(dp[n0 - c0][n1 - c1] + 1, dp[n0][n1])
return dp[m][n]
def threeD_findMaxForm(self, strs: List[str], m: int, n: int) -> int:
slen = len(strs)
dp = [[[0 for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(slen + 1)]
# dp[i][n0][n1] = max(dp[i-1][n0-count0(strs[i-1])][n1-count1(strs[i-1])] + 1,
# dp[i-1][n0][n1])
for i in range(1, slen + 1):
c0, c1 = count01(strs[i - 1])
# NOTE: n0 and n1 starts at 0, not 1
for n0 in range(m + 1):
for n1 in range(n + 1):
if n0 >= c0 and n1 >= c1:
dp[i][n0][n1] = max(dp[i - 1][n0 - c0][n1 - c1] + 1, dp[i - 1][n0][n1])
else:
dp[i][n0][n1] = dp[i - 1][n0][n1]
return dp[slen][m][n]
</syntaxhighlight>