企业官网建设流程全解析

LeetCode 一和零（Ones and Zeroes）题解：双约束 0/1 背包的四种 DP 递进解法

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇指南以 articles/ones-and-zeroes.md 为核心，系统讲解 LeetCode 474「一和零」：如何在给定m个0和n个1的预算内，从一组二进制字符串中选出最多数量的字符串。文章从暴力递归出发，逐步演进到记忆化搜索、三维自底向上 DP 与空间优化二维 DP，并对照本仓库 python/0474-ones-and-zeroes.py、cpp/0474-ones-and-zeroes.cpp、java/0474-ones-and-zeroes.java 等多语言实现，帮助读者真正掌握多维背包类问题的分析与优化套路。

前置知识

在动手之前，建议先掌握以下四块基础：

• 递归（Recursion）：能把问题拆解为更小的子问题，并正确写出基线条件（base case）。
• 0/1 背包动态规划：本题是经典背包问题的变体，区别在于约束条件从单一的「重量/容量」扩展为「0 的数量」与「1 的数量」两个维度。
• 记忆化（Memoization）：缓存子问题的计算结果，避免大量重复计算。
• 多维 DP（Multidimensional DP）：能够操作二维、三维 DP 表，因为本题的状态由三个变量共同刻画。

问题建模：从单约束背包到双约束背包

题目输入为字符串数组strs、预算m（最多可用的0个数）与n（最多可用的1个数）。对于每个字符串，我们必须决定「选」或「不选」，目标是最大化所选字符串的数量，且所选字符串中0的总数不超过m、1的总数不超过n。

这与经典 0/1 背包一一对应：字符串就是「物品」，字符串的 0/1 计数就是物品的「两种重量」，m与n就是两个独立的「容量」维度。物品只能选一次，因此属于 0/1 背包而非完全背包。

第一步是预处理：遍历每个字符串，统计其中0与1的数量，存入二维数组arr（约定下标0存0的个数、下标1存1的个数）。仓库各语言实现均采用这一预处理思路，例如 cpp/0474-ones-and-zeroes.cpp 用一个pair<int,int>数组保存每串的(zero, one)。

解法一：纯递归（暴力枚举所有组合）

思路

把每个字符串看作一个决策点：要么「跳过」，要么在预算足够时「纳入」。递归函数dfs(i, m, n)返回「从下标i开始、剩余m个 0 与n个 1 时最多还能选多少个字符串」。

算法步骤

1. 预处理每个字符串的 0/1 计数，存入arr。
2. 定义递归函数dfs(i, m, n)：
   • 基线条件：i到达数组末尾，返回0。
   • 分支一（跳过）：dfs(i + 1, m, n)。
   • 分支二（纳入，需m >= zeros且n >= ones）：1 + dfs(i + 1, m - zeros, n - ones)。
3. 返回两个分支的最大值。

代码（Python）

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: arr = [[0] * 2 for _ in range(len(strs))] for i, s in enumerate(strs): for c in s: arr[i][ord(c) - ord('0')] += 1 def dfs(i, m, n): if i == len(strs): return 0 res = dfs(i + 1, m, n) if m >= arr[i][0] and n >= arr[i][1]: res = max(res, 1 + dfs(i + 1, m - arr[i][0], n - arr[i][1])) return res return dfs(0, m, n)

仓库中的 cpp/0474-ones-and-zeroes.cpp 对该递归做了两处微调：当当前串的消耗已超出剩余预算时直接剪枝跳过（不再进入递归），并把「纳入 / 不纳入」命名为take/notTake，语义更直白。

复杂度

• 时间复杂度：$O(2 ^ N)$，每个字符串两种选择，指数爆炸。
• 空间复杂度：$O(N)$，来自递归调用栈。

其中 $N$ 为二进制字符串数量，$m$、$n$ 分别为 0 与 1 的最大可用个数。纯递归仅在 $N$ 很小时可行，它的价值在于为后续优化提供清晰的「无重复子问题假设」前的基准实现。

解法二：动态规划（自顶向下，记忆化）

思路

纯递归存在大量重叠子问题：同一状态(i, m, n)可能被多条不同路径反复到达，造成指数级冗余计算。引入记忆化后，每个唯一状态只计算一次。

算法步骤

1. 预处理各字符串的 0/1 计数。
2. 建立以(i, m, n)为键的三维记忆表。
3. dfs(i, m, n)逻辑同前，但先查缓存、命中即返回；否则计算后写回缓存。
4. 提前终止：若m == 0 and n == 0，已无任何预算，直接返回0。
5. 返回dfs(0, m, n)。

代码（Python）

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: arr = [[0] * 2 for _ in range(len(strs))] for i, s in enumerate(strs): for c in s: arr[i][ord(c) - ord('0')] += 1 dp = {} def dfs(i, m, n): if i == len(strs): return 0 if m == 0 and n == 0: return 0 if (i, m, n) in dp: return dp[(i, m, n)] res = dfs(i + 1, m, n) if m >= arr[i][0] and n >= arr[i][1]: res = max(res, 1 + dfs(i + 1, m - arr[i][0], n - arr[i][1])) dp[(i, m, n)] = res return res return dfs(0, m, n)

仓库实现验证了这一思路：python/0474-ones-and-zeroes.py 以字典缓存(i, m, n)状态；kotlin/0474-ones-and-zeroes.kt 用dp[m][n][i]三维数组做同样的事；cpp/0474-ones-and-zeroes.cpp 则使用(strs.size()+1) x (m+1) x (n+1)的三维数组并以-1初始化表示未计算。注意 Python/字典方案的内存仅覆盖实际访问到的状态，而三维数组方案会为所有组合预分配空间。

复杂度

• 时间复杂度：$O(m \times n \times N)$，每个状态(i, m, n)至多计算一次。
• 空间复杂度：$O(m \times n \times N)$，记忆表本身的开销（不含递归栈）。

解法三：动态规划（自底向上，三维表）

思路

把自顶向下改为迭代构建：逐个处理字符串，对每一种「剩余 0 预算 × 剩余 1 预算」组合，计算可获得的最大字符串数。定义dp[i][j][k]为「从前i个字符串中，最多使用j个 0 与k个 1 时能选出的最大字符串数」。

算法步骤

1. 预处理各字符串的 0/1 计数。
2. 建立(len(strs) + 1) x (m + 1) x (n + 1)的三维表，初值全为0。
3. 对每个i（从1到len(strs)）：
   • 遍历 0 预算j（0到m）与 1 预算k（0到n）：
     • 先继承「不选当前串」的结果：dp[i][j][k] = dp[i-1][j][k]；
     • 若j >= zeros且k >= ones，尝试「选当前串」：dp[i][j][k] = max(dp[i][j][k], 1 + dp[i-1][j-zeros][k-ones])。
4. 返回dp[len(strs)][m][n]。

代码（Python）

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: arr = [[0] * 2 for _ in range(len(strs))] for i, s in enumerate(strs): for c in s: arr[i][ord(c) - ord('0')] += 1 dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)] for i in range(1, len(strs) + 1): for j in range(m + 1): for k in range(n + 1): dp[i][j][k] = dp[i - 1][j][k] if j >= arr[i - 1][0] and k >= arr[i - 1][1]: dp[i][j][k] = max(dp[i][j][k], 1 + dp[i - 1][j - arr[i - 1][0]][k - arr[i - 1][1]]) return dp[len(strs)][m][n]

该写法保留了完整的「物品维度」，便于在需要回溯输出具体选了哪些字符串时使用；代价是空间占用随N线性增长。

复杂度

• 时间复杂度：$O(m \times n \times N)$。
• 空间复杂度：$O(m \times n \times N)$。

解法四：动态规划（空间优化，二维表 + 逆序迭代）

思路

观察三维递推式可知：计算dp[i]只依赖dp[i-1]这一层，因此三维表可压缩为二维表dp[j][k]。关键在于预算必须逆序迭代：更新dp[j][k]时要用到上一轮（尚未被当前字符串污染）的dp[j-zeros][k-ones]；从大到小遍历可确保这些旧值在本轮迭代中未被覆盖，从而保证每个字符串最多被选中一次。

算法步骤

1. 预处理各字符串的 0/1 计数。
2. 建立(m + 1) x (n + 1)的二维表，初值全为0。
3. 对每个含zeros个 0、ones个 1 的字符串：
   • j从m递减到zeros，k从n递减到ones：
     • dp[j][k] = max(dp[j][k], 1 + dp[j-zeros][k-ones])。
4. 返回dp[m][n]。

代码（Python）

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: arr = [[0, 0] for _ in range(len(strs))] for i, s in enumerate(strs): for c in s: arr[i][ord(c) - ord('0')] += 1 dp = [[0] * (n + 1) for _ in range(m + 1)] for zeros, ones in arr: for j in range(m, zeros - 1, -1): for k in range(n, ones - 1, -1): dp[j][k] = max(dp[j][k], 1 + dp[j - zeros][k - ones]) return dp[m][n]

这是竞赛与面试中最推荐的写法，也是本仓库多数语言实现采用的形式：java/0474-ones-and-zeroes.java 与 typescript/0474-ones-and-zeroes.ts 使用(m+1) x (n+1)二维数组逆序更新；kotlin/0474-ones-and-zeroes.kt 用m downTo zeros/n downTo ones区间表达逆序；swift/0474-ones-and-zeroes.swift 以字典[i, j] -> count实现，未访问过的状态按0处理；python/0474-ones-and-zeroes.py 则用defaultdict(int)配合同样的逆序双循环。各实现的时间复杂度一致，仅在内存表示与访问方式上有所差异。

复杂度

• 时间复杂度：$O(m \times n \times N)$。
• 空间复杂度：$O(m \times n + N)$，其中+N来自预处理得到的arr计数数组。

四种解法复杂度对照

常见陷阱

陷阱一：空间优化 DP 中正序而非逆序迭代

使用二维空间优化解法时，若从0到m（或0到n）正向迭代，同一字符串会在一次遍历中被重复计入多次，等同于错误地把 0/1 背包当成了完全背包。必须令j从m递减到zeros、k从n递减到ones，才能保证每个字符串至多被选中一次。这一点在 java/0474-ones-and-zeroes.java 与 python/0474-ones-and-zeroes.py 的循环写法中均有体现。

陷阱二：混淆 0 与 1 的计数

把「0 的个数」与「1 的个数」存入错误的数组下标，会导致预算检查整体错乱。解决方案是全程统一约定：下标0存 0 的个数、下标1存 1 的个数（或反向统一），并确保所有比较与更新都遵循同一约定。例如 cpp/0474-ones-and-zeroes.cpp 明确将{zero, one}存入pair，而 typescript/0474-ones-and-zeroes.ts 用[zeroes, str.length - zeroes]构造对偶。

陷阱三：把本题当作完全背包

本题是严格的 0/1 背包：每个字符串只能选一次。任何允许同一字符串被多次选择的解法都会高估答案。正确做法是让每个字符串恰好被处理一次（选中或跳过）——这正是三维 DP 中i维度逐层推进、以及空间优化解法中逆序迭代所要保证的性质。

仓库源码对照与延伸阅读

本仓库为「一和零」提供了多语言、多思路的完整实现，可与本文四种解法逐一对照：

• python/0474-ones-and-zeroes.py：同时给出「字典 + 逆序迭代」的空间优化 DP 与「记忆化递归」两种写法。
• cpp/0474-ones-and-zeroes.cpp：自顶向下记忆化递归，含超预算剪枝。
• java/0474-ones-and-zeroes.java：二维数组空间优化 DP。
• kotlin/0474-ones-and-zeroes.kt：同一文件内注释区分「Recursion with memoization」与「DP solution」两个版本。
• swift/0474-ones-and-zeroes.swift：以字典实现空间优化 DP。
• typescript/0474-ones-and-zeroes.ts：二维数组空间优化 DP，含undefined兜底初始化。

若想巩固双约束背包的变式，可继续研读本仓库中同属多维 DP 思路的题解，如 articles/partition-equal-subset-sum.md（单约束 0/1 背包）与 articles/target-sum.md（0/1 背包计数变体），以横向对比约束维度从一维扩展到二维时状态定义与空间优化手法的演进。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode