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缓存子问题的计算结果避免大量重复计算。多维 DPMultidimensional 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 用一个pairint,int数组保存每串的(zero, one)。解法一纯递归暴力枚举所有组合思路把每个字符串看作一个决策点要么「跳过」要么在预算足够时「纳入」。递归函数dfs(i, m, n)返回「从下标i开始、剩余m个 0 与n个 1 时最多还能选多少个字符串」。算法步骤预处理每个字符串的 0/1 计数存入arr。定义递归函数dfs(i, m, n)基线条件i到达数组末尾返回0。分支一跳过dfs(i 1, m, n)。分支二纳入需m zeros且n ones1 dfs(i 1, m - zeros, n - ones)。返回两个分支的最大值。代码Pythonclass 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)可能被多条不同路径反复到达造成指数级冗余计算。引入记忆化后每个唯一状态只计算一次。算法步骤预处理各字符串的 0/1 计数。建立以(i, m, n)为键的三维记忆表。dfs(i, m, n)逻辑同前但先查缓存、命中即返回否则计算后写回缓存。提前终止若m 0 and n 0已无任何预算直接返回0。返回dfs(0, m, n)。代码Pythonclass 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 (m1) x (n1)的三维数组并以-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 时能选出的最大字符串数」。算法步骤预处理各字符串的 0/1 计数。建立(len(strs) 1) x (m 1) x (n 1)的三维表初值全为0。对每个i从1到len(strs)遍历 0 预算j0到m与 1 预算k0到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])。返回dp[len(strs)][m][n]。代码Pythonclass 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]从大到小遍历可确保这些旧值在本轮迭代中未被覆盖从而保证每个字符串最多被选中一次。算法步骤预处理各字符串的 0/1 计数。建立(m 1) x (n 1)的二维表初值全为0。对每个含zeros个 0、ones个 1 的字符串j从m递减到zerosk从n递减到onesdp[j][k] max(dp[j][k], 1 dp[j-zeros][k-ones])。返回dp[m][n]。代码Pythonclass 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 使用(m1) x (n1)二维数组逆序更新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计数数组。四种解法复杂度对照解法思路时间复杂度空间复杂度适用场景纯递归枚举所有「选 / 不选」组合$O(2^N)$$O(N)$栈仅用于理解问题结构自顶向下 DP递归 记忆化$O(m \times n \times N)$$O(m \times n \times N)$状态稀疏、只想计算实际访问到的状态自底向上三维 DP迭代填表保留物品维度$O(m \times n \times N)$$O(m \times n \times N)$需要回溯具体方案空间优化二维 DP逆序迭代复用单层表$O(m \times n \times N)$$O(m \times n N)$只求最大数量内存敏感场景常见陷阱陷阱一空间优化 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.md0/1 背包计数变体以横向对比约束维度从一维扩展到二维时状态定义与空间优化手法的演进。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 一和零（Ones and Zeroes）题解：双约束 0/1 背包的四种 DP 递进解法
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缓存子问题的计算结果避免大量重复计算。多维 DPMultidimensional 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 用一个pairint,int数组保存每串的(zero, one)。解法一纯递归暴力枚举所有组合思路把每个字符串看作一个决策点要么「跳过」要么在预算足够时「纳入」。递归函数dfs(i, m, n)返回「从下标i开始、剩余m个 0 与n个 1 时最多还能选多少个字符串」。算法步骤预处理每个字符串的 0/1 计数存入arr。定义递归函数dfs(i, m, n)基线条件i到达数组末尾返回0。分支一跳过dfs(i 1, m, n)。分支二纳入需m zeros且n ones1 dfs(i 1, m - zeros, n - ones)。返回两个分支的最大值。代码Pythonclass 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)可能被多条不同路径反复到达造成指数级冗余计算。引入记忆化后每个唯一状态只计算一次。算法步骤预处理各字符串的 0/1 计数。建立以(i, m, n)为键的三维记忆表。dfs(i, m, n)逻辑同前但先查缓存、命中即返回否则计算后写回缓存。提前终止若m 0 and n 0已无任何预算直接返回0。返回dfs(0, m, n)。代码Pythonclass 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 (m1) x (n1)的三维数组并以-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 时能选出的最大字符串数」。算法步骤预处理各字符串的 0/1 计数。建立(len(strs) 1) x (m 1) x (n 1)的三维表初值全为0。对每个i从1到len(strs)遍历 0 预算j0到m与 1 预算k0到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])。返回dp[len(strs)][m][n]。代码Pythonclass 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]从大到小遍历可确保这些旧值在本轮迭代中未被覆盖从而保证每个字符串最多被选中一次。算法步骤预处理各字符串的 0/1 计数。建立(m 1) x (n 1)的二维表初值全为0。对每个含zeros个 0、ones个 1 的字符串j从m递减到zerosk从n递减到onesdp[j][k] max(dp[j][k], 1 dp[j-zeros][k-ones])。返回dp[m][n]。代码Pythonclass 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 使用(m1) x (n1)二维数组逆序更新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计数数组。四种解法复杂度对照解法思路时间复杂度空间复杂度适用场景纯递归枚举所有「选 / 不选」组合$O(2^N)$$O(N)$栈仅用于理解问题结构自顶向下 DP递归 记忆化$O(m \times n \times N)$$O(m \times n \times N)$状态稀疏、只想计算实际访问到的状态自底向上三维 DP迭代填表保留物品维度$O(m \times n \times N)$$O(m \times n \times N)$需要回溯具体方案空间优化二维 DP逆序迭代复用单层表$O(m \times n \times N)$$O(m \times n N)$只求最大数量内存敏感场景常见陷阱陷阱一空间优化 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.md0/1 背包计数变体以横向对比约束维度从一维扩展到二维时状态定义与空间优化手法的演进。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考