企业官网建设流程全解析

LeetCode-Go 题解 | 474. Ones and Zeroes：二维 01 背包问题的 Go 实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 第 474 题 "Ones and Zeroes"（一和零）为核心，讲解如何把"在 m 个 0 与 n 个 1 的限额下挑选最多字符串"这一经典问题建模为二维 01 背包并给出 Go 实现。文章以本仓库中该题对应的 README.md 为骨架，结合 474. Ones and Zeroes.go 的源码与 474. Ones and Zeroes_test.go 的测试用例逐层展开。读完本文，你将掌握二维背包的状态定义、逆序遍历防重复使用的原理，以及如何使用strings.Count高效统计字符串中 0/1 的个数，并能在本地运行仓库测试复现结果。

题目回顾

在计算机世界中，我们总是追求用有限的资源获取最大的收益。现在假设你分别支配着m个0和n个1，同时给定一个仅由0和1组成的字符串数组。你的任务是：使用给定的 m 个0和 n 个1，找出能拼出的存在于数组中的字符串的最大数量。每个0和1至多被使用一次。

注意（题目约束）：

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

示例 1：

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 Output: 4

解释：使用 5 个0和 3 个1，可以拼出"10"、"0001"、"1"、"0"这 4 个字符串，恰好耗尽 5 个0（"10"占 1 个、"0001"占 3 个、"0"占 1 个）与 3 个1（"10"占 1 个、"0001"占 1 个、"1"占 1 个）。

示例 2：

Input: Array = {"10", "0", "1"}, m = 1, n = 1 Output: 2

解释：可以拼出"10"，但之后就没有任何0或1剩余；更好的选择是拼出"0"和"1"这两个字符串。

题目大意

把原题翻译成大白话就是：给定一个字符串数组以及两个容量 m、n，其中所有字符串都由0和1组成。问能否从数组中取出最多的字符串，使得这些被取出的字符串中所有0的个数 ≤ m，所有1的个数 ≤ n。每个字符串要么整体被取走、要么完全不被取走，不能被拆开部分使用。

解题思路：二维 01 背包建模

本题在 README.md 中明确指出是典型的 01 背包题型，只不过是一个二维背包问题：普通的 01 背包只有一个容量维度，而这里同时存在"0 的个数"和"1 的个数"两个约束维度。可以把问题等价地理解为：在 n 个物品中选出若干物品，尽量完全填满m 维和 n 维的背包。

为什么是"尽量填满"而不是"必须填满"？因为不一定能恰好用完所有资源，例如示例 2 中 m = 1、n = 1 时，选"10"虽然"填满"了背包，但只能得到 1 个字符串；而选"0"和"1"得到 2 个字符串，反而更优。这说明目标函数是最大化物品数量，而不是最大化资源占用。

状态定义与转移方程

定义：

dp[i][j] = 尽量填满容量为 (i, j) 的背包装下的物品总数

其中第一维 i 表示可用的0的个数，第二维 j 表示可用的1的个数。状态转移方程为：

dp[i][j] = max(dp[i][j], 1 + dp[i-zero][j-one])

• zero表示当前要装入的物品在 m 维上的"体积"，即该字符串中0的个数；
• one表示当前要装入的物品在 n 维上的"体积"，即该字符串中1的个数。

每次尝试装入一个新物品时，比较两种选择：不装该物品（保持dp[i][j]不变），或者装入该物品（即(i-zero, j-one)容量背包下的最优解再加 1，因为多装了一个字符串），取两者的较大值。每扫描完一个物品就刷新整个二维背包，直到所有物品都处理完毕，最终dp[m][n]中存储的就是答案。

为什么必须逆序遍历

在 01 背包中，每个物品至多选一次。如果 i、j 从0到m、n正序遍历，那么更新dp[i][j]时使用的dp[i-zero][j-one]可能已经在当前物品的同一轮中被更新过，相当于同一个字符串被重复使用了多次，这就退化成"完全背包"。因此必须**从大到小（逆序）**遍历 i 和 j，保证dp[i-zero][j-one]是上一轮（未装入当前物品时）的状态。这一点在 474. Ones and Zeroes.go 第 16-19 行的双重循环中得到了严格执行。

仓库源码逐行解析

本题的完整 Go 实现在 474. Ones and Zeroes.go 中，核心函数为findMaxForm(strs []string, m int, n int) int：

func findMaxForm(strs []string, m int, n int) int { dp := make([][]int, m+1) for i := 0; i < m+1; i++ { dp[i] = make([]int, n+1) } for _, s := range strs { zero := strings.Count(s, "0") one := len(s) - zero if zero > m || one > n { continue } for i := m; i >= zero; i-- { for j := n; j >= one; j-- { dp[i][j] = max(dp[i][j], 1+dp[i-zero][j-one]) } } } return dp[m][n] }

下面按代码执行顺序逐段解读：

1. 初始化二维 DP 表（第 6-9 行）

dp是一个(m+1) × (n+1)的二维切片，dp[i][j]默认值为 0，表示容量为(i, j)时最初一个物品都没装入。注意维度比输入 m、n 各多 1，是为了覆盖"容量为 0"的情况（即dp[0][0] = 0）。

2. 统计每个字符串的 0/1 个数（第 10-12 行）

zero := strings.Count(s, "0") one := len(s) - zero

这里利用 Go 标准库strings.Count一次遍历统计出0的个数，然后用字符串总长度减去0的个数即得1的个数。由于题目保证字符串只含0和1，这个减法始终成立，且比再调用一次strings.Count(s, "1")更高效。

3. 剪枝优化（第 13-15 行）

if zero > m || one > n { continue }

如果一个字符串对0或1的需求量已经超过总限额，那么无论如何它都不可能被选中，直接跳过，可以省去一轮完全无效的背包刷新。

4. 逆序双层循环执行状态转移（第 16-20 行）

for i := m; i >= zero; i-- { for j := n; j >= one; j-- { dp[i][j] = max(dp[i][j], 1+dp[i-zero][j-one]) } }

外层循环遍历每一个字符串（物品），内层两层循环从大到小遍历两个容量维度，实现"每个物品至多使用一次"的 01 背包语义。i >= zero与j >= one是循环边界，保证下标不会越界。

5. 辅助函数 max（第 25-29 行）

func max(a int, b int) int { if a > b { return a } return b }

该函数是题解文件中独立实现的局部辅助函数，用于比较"不装当前物品"与"装入当前物品"两种决策的收益，取较大者写回dp[i][j]。

测试用例验证

仓库为本题配套了 474. Ones and Zeroes_test.go，测试结构采用参数化用例：para474封装输入（strs、m、n），ans474封装期望输出。Test_Problem474覆盖了 4 组用例：

最后一组用例值得手动推演验证：m = 4、n = 2 时，"0"、"00"、"000"合计恰好用掉 4 个0，"1"、"11"合计恰好用掉 2 个1，全部 5 个字符串理论上总需求为 6 个0+ 3 个1，超出限额，所以最优解是各取一部分凑成 4 个，与期望输出一致。测试通过fmt.Printf打印每组输入与findMaxForm的实际输出，便于对照调试。整个仓库统一通过 gotest.sh 中的go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...方式运行全部题解测试并收集覆盖率数据，本项目模块定义在 go.mod（modulegithub.com/halfrost/LeetCode-Go，Go 版本 1.19），在仓库根目录执行go test ./leetcode/0474.Ones-and-Zeroes/...即可单独运行本题的测试。

复杂度分析

• 时间复杂度：O(len(strs) × m × n)。对每个字符串都要做一次O(m × n)的二维 DP 刷新，再加上统计 0/1 个数所需的O(len(s))字符串遍历，整体量级为O(N × M × N)（N 为字符串个数），与 README.md 中给出的O(n * M * N)复杂度结论一致；
• 空间复杂度：O(m × n)，来自(m+1) × (n+1)的 DP 表。得益于逆序遍历，无需额外保存"上一轮"的完整状态副本，单张 DP 表即可完成滚动更新。

总结

LeetCode 474 "Ones and Zeroes" 是二维 01 背包的经典入门题，其核心建模要点可以归纳为三条：

1. 把两种资源（0 的个数、1 的个数）抽象成两个背包维度，状态dp[i][j]表示在容量(i, j)下能装入的最大字符串数量；
2. 状态转移采用dp[i][j] = max(dp[i][j], 1 + dp[i-zero][j-one])，比较装与不装当前字符串的收益；
3. 逆序遍历两个容量维度，保证每个字符串至多被选中一次，这是 01 背包与完全背包的本质区别。

配合本仓库 474. Ones and Zeroes.go 的源码实现，可以看到项目在常规 DP 之外还加入了strings.Count快速统计与"需求超限即跳过"的剪枝细节，使代码兼具正确性与效率。掌握本题后，遇到"两种资源限额下求最大收益"的变体题（例如资源配额、预算双约束的选择问题），都可以沿袭这套二维背包的建模与实现思路。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go