# \[474]\[中等]\[动态规划]\[背包] 一和零

## 题目描述

[474. 一和零](https://leetcode-cn.com/problems/ones-and-zeroes/)

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

* 给定 0 和 1 的数量都不会超过 100。
* 给定字符串数组的长度不会超过 600。

示例 1:

```
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
```

示例 2:

```
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2

解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
```

## 解题思路

本题是将01背包问题, 推广到二维的情况. 列表中的每一个字符串代表一个物品, 背包的容量从一维扩展到二维, 因此, 在状态转移的时候要考虑两个维度. 所以状态转移矩阵是三维的.

下面的代码使用了**滚动数组**, 在字符串(物品)维度上进行滚动, 将状态转移矩阵简化为二维.

```python
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        zeros = [sum(1 for c in s if c == '0') for s in strs]
        ones = [sum(1 for c in s if c == '1') for s in strs]

        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for k, _ in enumerate(strs):
            zero, one = zeros[k], ones[k]
            for i in range(n, one - 1, -1):
                for j in range(m, zero - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - one][j - zero] + 1)
        return dp[-1][-1]
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/474-yi-he-ling.md?ask=<question>
```

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.