> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/474.-ones-and-zeroes.md).

# 474. Ones and Zeroes

## LeetCode [474. Ones and Zeroes](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

You are given an array of binary strings `strs` and two integers `m` and `n`.

Return *the size of the largest subset of`strs` such that there are **at most*** `m` **`0`** ***' s and*** **`n`** `1` *' s in the subset*.

A set `x` is a **subset** of a set `y` if all elements of `x` are also elements of `y`.

**Example 1:**

```
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
```

**Example 2:**

```
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
```

**Constraints:**

* `1 <= strs.length <= 600`
* `1 <= strs[i].length <= 100`
* `strs[i]` consists only of digits `'0'` and `'1'`.
* `1 <= m, n <= 100`

### Tags

Dynamic Programming

### Solution

这道题和经典的背包问题很类似，不同之处体现在这道题有两种容量。用 `dp(i, j)` 表示容量为 `i` 个 0 和 `j` 个 1时集合的最大长度，那么状态转移方程为：

`dp(i, j) = max(1 + dp(i - cost_0[k], j - cost_1[k])) if i >= cost_0[k] and j >= cost_1[k]`

`k`代表第`k`个字符串，因此我们遍历每个字符串，统计他的`cost_0`和`cost_1`，从大到小进行枚举。最后返回`dp[m][n]`，表示两种容量分别为`m`和`n`时最大的集合长度。

This question is a variant of Knapsack problem, but the difference is that this problem has two types of capacities. We use `dp(i, j)` to represent the longest length when 0's capacity is `i` and 1's is `j`. We formulate the transform function as:

`dp(i, j) = max(1 + dp(i - cost_0[k], j - cost_1[k])) if i >= cost_0[k] and j >= cost_1[k]`

We denote `k` as the kth string, so we iterate over the string slice and count the number of 0 and 1, as `cost_0` and `cost_1` respectively, appearing in each string. Enumerate from high capacity to low. Finally, we return `dp[m][n]`.

### Complexity

* Time complexity: $$O(mnl)$$
* Space complexity: $$O(mn)$$

### Code

```go
func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for _, s := range strs {
		var n0, n1 int
		for _, c := range s {
			if c == '0' {
				n0++
			} else {
				n1++
			}
		}
		for i := m; i >= n0; i-- {
			for j := n; j >= n1; j-- {
				if v := 1 + dp[i-n0][j-n1]; dp[i][j] < v {
					dp[i][j] = v
				}
			}
		}
	}
	return dp[m][n]
}
```

## Reference

1. [一和零](https://leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode/)