# 一和零
 [](https://imhuay.gitbook.io/studies/algorithms/..#中等) [](https://imhuay.gitbook.io/studies/algorithms/..#leetcode) [](https://imhuay.gitbook.io/studies/algorithms/..#动态规划) [](https://imhuay.gitbook.io/studies/algorithms/..#暴力递归与动态规划)
**问题简述**
```
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
```
> [474. 一和零 - 力扣（LeetCode）](https://leetcode-cn.com/problems/ones-and-zeroes/)
**思路：自底向上递归+记忆化搜索**
* 定义 `dfs(i, rest_z, rest_o)` 表示剩余容量为 `rest_z`, `rest_o` 情况下，前 `i` 个元素的最大子集长度（子问题）；
* 【递归基】显然 `i=0` 时，返回 `0`；
* 然后分是否加入当前元素，返回其中的最大值；
* 记得预处理所有字符串；
Python
```python
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
from functools import lru_cache
def get_zo(s):
z, o = 0, 0
for c in s:
if c == '0': z += 1
else: o += 1
return z, o
# 预处理
tb = dict()
for s in strs:
tb[s] = get_zo(s)
@lru_cache(maxsize=None)
def dfs(i, rest_z, rest_o): # 剩余容量为 rest_z, rest_o 情况下，strs[:i] 下的最大子集长度
if i == 0:
return 0
c1 = dfs(i - 1, rest_z, rest_o) # 不要
c2 = 0
z, o = tb[strs[i - 1]]
if rest_z >= z and rest_o >= o: # 要
c2 = dfs(i - 1, rest_z - z, rest_o - o) + 1
return max(c1, c2)
N = len(strs)
return dfs(N, m, n)
```
**优化**：通过递归转动态规划
> 实际上，记忆化搜索的速度要更快；
Python
```python
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
from functools import lru_cache
def get_zo(s):
z, o = 0, 0
for c in s:
if c == '0': z += 1
else: o += 1
return z, o
N = len(strs)
# 预处理
tb = dict()
for s in strs:
tb[s] = get_zo(s)
# dp[N][m][n]
dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
for rest_z in range(m + 1):
for rest_o in range(n + 1):
c1 = dp[i - 1][rest_z][rest_o]
c2 = 0
z, o = tb[strs[i - 1]]
if rest_z >= z and rest_o >= o:
c2 = dp[i - 1][rest_z - z][rest_o - o] + 1
dp[i][rest_z][rest_o] = max(c1, c2)
return dp[N][m][n]
```
**空间优化**（略）
> [【宫水三叶】详解如何转换「背包问题」，以及逐步空间优化 - 一和零 - 力扣（LeetCode）](https://leetcode-cn.com/problems/ones-and-zeroes/solution/gong-shui-san-xie-xiang-jie-ru-he-zhuan-174wv/)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/leetcode0474-zhong-deng-yi-he-ling.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.