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

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至多被使用一次。注意题目约束给定的0和1的数量都不会超过100给定字符串数组的长度不会超过600。示例 1Input: Array {10, 0001, 111001, 1, 0}, m 5, n 3 Output: 4解释使用 5 个0和 3 个1可以拼出10、0001、1、0这 4 个字符串恰好耗尽 5 个010占 1 个、0001占 3 个、0占 1 个与 3 个110占 1 个、0001占 1 个、1占 1 个。示例 2Input: 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) intfunc findMaxForm(strs []string, m int, n int) int { dp : make([][]int, m1) for i : 0; i m1; i { dp[i] make([]int, n1) } 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], 1dp[i-zero][j-one]) } } } return dp[m][n] }下面按代码执行顺序逐段解读1. 初始化二维 DP 表第 6-9 行dp是一个(m1) × (n1)的二维切片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], 1dp[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、nans474封装期望输出。Test_Problem474覆盖了 4 组用例输入 strsmn期望输出用例考察点{10, 0001, 111001, 1, 0}534题目原始示例 1{10, 0, 1}112题目原始示例 2验证尽量填满而非必须填满{}空数组000边界没有任何可用字符串{0, 00, 000, 1, 11}424多种组合选择下求最大数量最后一组用例值得手动推演验证m 4、n 2 时0、00、000合计恰好用掉 4 个01、11合计恰好用掉 2 个1全部 5 个字符串理论上总需求为 6 个0 3 个1超出限额所以最优解是各取一部分凑成 4 个与期望输出一致。测试通过fmt.Printf打印每组输入与findMaxForm的实际输出便于对照调试。整个仓库统一通过 gotest.sh 中的go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...方式运行全部题解测试并收集覆盖率数据本项目模块定义在 go.modmodulegithub.com/halfrost/LeetCode-GoGo 版本 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)来自(m1) × (n1)的 DP 表。得益于逆序遍历无需额外保存上一轮的完整状态副本单张 DP 表即可完成滚动更新。总结LeetCode 474 Ones and Zeroes 是二维 01 背包的经典入门题其核心建模要点可以归纳为三条把两种资源0 的个数、1 的个数抽象成两个背包维度状态dp[i][j]表示在容量(i, j)下能装入的最大字符串数量状态转移采用dp[i][j] max(dp[i][j], 1 dp[i-zero][j-one])比较装与不装当前字符串的收益逆序遍历两个容量维度保证每个字符串至多被选中一次这是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考