企业官网建设流程全解析

LeetCode 474 Ones and Zeroes 题解：从暴力递归到二维 0-1 背包 DP 的四步优化

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本文基于 problems/474.ones-and-zeros-en.md 展开，讲解 LeetCode 474「一和零（Ones and Zeroes）」这一经典多维 0-1 背包问题。文章以原文档的四级解法（暴力递归 → 记忆化递归 → 3D DP → 2D DP）为骨架，结合本仓库的动态规划讲义与背包问题专题，完整给出 Java / Python3 可运行代码、状态定义、转移方程与复杂度推导。读完你将掌握：如何识别多维背包问题、如何从暴力解逐步优化出滚动数组版本的 DP，以及面试中从「能跑」到「最优」的递进式解题节奏。

一、题目：资源受限下最大化收益

在计算机世界中，用受限资源去获取最大收益是我们始终追求的目标。本题正是一个抽象后的资源分配模型：

• 你分别拥有m 个 0和n 个 1两种资源；
• 给定一个仅由0和1组成的字符串数组strs；
• 每个字符串都可以被「形成」（即使用），但每个 0 和每个 1 最多只能使用一次；
• 目标：求出在 m 个 0 与 n 个 1 的约束下，最多能形成多少个字符串。

题目约束（决定了算法设计空间）：

示例 1

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

"10"、"0001"、"1"、"0"共 4 个字符串恰好可被形成（分别消耗 5 个 0 与 3 个 1）。

示例 2

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

若只形成"10"，剩余资源为 0；更优的选择是形成"0"和"1"两个字符串，说明需要全局决策而非贪心。

二、解题思路：为什么这是一道 0-1 背包

原文档给出的判断非常直接：凡是要求返回最大值、最大长度等「最优值」且不要求列出所有可行方案的题目，通常都可以用 DP 求解。本题满足这一特征，并且可以归约为经典的0-1 背包：对每个字符串只有「取」或「不取」两种决策，且每种资源每个单位最多用一次。

对应到本仓库背包问题专题给出的背包描述：有 N 件物品与容量为 V 的背包，放入第 i 件物品耗费费用 Ci、获得价值 Wi，求价值最大的装入方案，转移方程为

F[i, v] = max(F[i-1, v], F[i-1, v-Ci] + Wi)

本题的特殊之处在于背包有两个容量维度（0 的数量与 1 的数量），每件「物品」是字符串，其「费用」为(count0, count1)，「价值」为 1（多形成一个字符串）。这属于二维费用的 0-1 背包。

面试技巧（原文档原话要点）：面试现场 DP 很难立刻想到，建议先给出暴力解，再逐步优化，直到面试官满意。下面按原文档给出的 4 个解法依次展开。

三、Solution #1：暴力递归（Brute Force）

暴力法的思路是枚举strs的所有子集（共2^len个），对每个子集统计其中0和1的总数，用全局变量max记录满足count(0) <= m && count(1) <= n的最大子集大小。

递归实现中，对每个字符串做「取 / 不取」二分，idx表示当前处理到第几个字符串，j / k表示剩余可用的 0 / 1 数量：

Java

class OnesAndZerosBFRecursive { public int findMaxForm2(String[] strs, int m, int n) { return helper(strs, 0, m, n); } private int helper(String[] strs, int idx, int j, int k) { if (idx == strs.length) return 0; // 统计当前字符串中 0 和 1 的个数 int[] counts = countZeroOnes(strs[idx]); // 若剩余资源足够，取当前字符串：资源相应减少，计数 +1 int takeCurrStr = j - counts[0] >= 0 && k - counts[1] >= 0 ? 1 + helper(strs, idx + 1, j - counts[0], k - counts[1]) : -1; // 不取当前字符串，继续处理下一个 int notTakeCurrStr = helper(strs, idx + 1, j, k); return Math.max(takeCurrStr, notTakeCurrStr); } private int[] countZeroOnes(String s) { int[] res = new int[2]; for (char ch : s.toCharArray()) { res[ch - '0']++; } return res; } }

Python3

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: return self.helper(strs, m, n, 0) def helper(self, strs, m, n, idx): if idx == len(strs): return 0 take_curr_str = -1 count0, count1 = strs[idx].count('0'), strs[idx].count('1') if m >= count0 and n >= count1: take_curr_str = max(take_curr_str, self.helper(strs, m - count0, n - count1, idx + 1) + 1) not_take_curr_str = self.helper(strs, m, n, idx + 1) return max(take_curr_str, not_take_curr_str)

复杂度分析

• 时间复杂度:O(2^len * s)—— len 为字符串数组长度，s 为字符串平均长度（每次递归都要扫描一次字符串统计 0/1）
• 空间复杂度:O(1)（不计递归调用栈）

该解法在 LeetCode 上会 TLE（超时），仅作为兜底/思路起点。

四、Solution #2：记忆化 + 递归（Memorization）

暴力递归之所以慢，是因为大量子问题被重复计算：不同的「取 / 不取」组合可能落在相同的(idx, j, k)状态上。这正是本仓库动态规划讲义反复强调的重叠子问题——递归函数满足「参数确定则返回值确定」的数学函数性质，因此可以把已算过的状态存入 memo 表，再次遇到直接返回。

memo 定义：

memo[i][j][k] —— 在前 [0, i] 个字符串范围内，用 j 个 0 和 k 个 1 最多能形成的字符串数

helper(strs, i, j, k, memo)递归逻辑：

1. 若memo[i][j][k] != 0，说明该状态已计算过，直接返回；
2. 否则统计strs[i]的count0 / count1，若count0 <= j && count1 <= k，则取当前字符串，递归helper(strs, i+1, j-count0, k-count1, memo)；
3. 不取当前字符串，递归helper(strs, i+1, j, k, memo)；
4. 将两者较大值写入memo[i][j][k]并返回。

Java

class OnesAndZerosMemoRecur { public int findMaxForm4(String[] strs, int m, int n) { return helper(strs, 0, m, n, new int[strs.length][m + 1][n + 1]); } private int helper(String[] strs, int idx, int j, int k, int[][][] memo) { if (idx == strs.length) return 0; // 已计算过则直接返回 if (memo[idx][j][k] != 0) { return memo[idx][j][k]; } int[] counts = countZeroOnes(strs[idx]); // 满足条件则取当前字符串，更新剩余 0/1 数量 int takeCurrStr = j - counts[0] >= 0 && k - counts[1] >= 0 ? 1 + helper(strs, idx + 1, j - counts[0], k - counts[1], memo) : -1; // 不取当前字符串 int notTakeCurrStr = helper(strs, idx + 1, j, k, memo); // 始终把最大值写入记忆表 memo[idx][j][k] = Math.max(takeCurrStr, notTakeCurrStr); return memo[idx][j][k]; } private int[] countZeroOnes(String s) { int[] res = new int[2]; for (char ch : s.toCharArray()) { res[ch - '0']++; } return res; } }

Python3（原文档标注该写法在 LeetCode 上仍可能 TLE，Python 递归开销较大，建议工程上改用迭代 DP）

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: memo = {k:[[0]*(n+1) for _ in range(m+1)] for k in range(len(strs)+1)} return self.helper(strs, 0, m, n, memo) def helper(self, strs, idx, m, n, memo): if idx == len(strs): return 0 if memo[idx][m][n] != 0: return memo[idx][m][n] take_curr_str = -1 count0, count1 = strs[idx].count('0'), strs[idx].count('1') if m >= count0 and n >= count1: take_curr_str = max(take_curr_str, self.helper(strs, idx + 1, m - count0, n - count1, memo) + 1) not_take_curr_str = self.helper(strs, idx + 1, m, n, memo) memo[idx][m][n] = max(take_curr_str, not_take_curr_str) return memo[idx][m][n]

复杂度分析

• 时间复杂度:O(l * m * n)—— l 为 strs 长度，m 为 0 的数量上限，n 为 1 的数量上限
• 空间复杂度:O(l * m * n)—— 3D memo 数组

与暴力法的O(2^len)相比，状态数从指数级降为多项式级，这正是记忆化消除重叠子问题的收益。关于「状态总数 ≈ 各参数取值范围的笛卡尔积」这一 DP 复杂度规律，可参见动态规划讲义中的详细推导。

五、Solution #3：3D DP（自底向上迭代）

记忆化递归是「自顶向下 + 查表」，3D DP 则是把同样的状态转移改写成自底向上的三重循环。二者在思想上等价（DP 表与 memo 表本质相同），区别仅在于用迭代替代递归调用栈枚举状态。

dp 定义：

dp[i][j][k] —— 在 [0, i] 范围内字符串中，用 j 个 0 和 k 个 1 最多能形成的字符串数

状态转移方程（count0 / count1为strs[i]中 0 / 1 的个数）：

• 当j >= count0 && k >= count1（资源足够，取或不取取更优）：

  dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-count0][k-count1] + 1)

• 否则（资源不足，只能不取）：

  dp[i][j][k] = dp[i-1][j][k]

最终答案即为dp[l][m][n]。

Java

class OnesAndZeros3DDP { public int findMaxForm(String[] strs, int m, int n) { int l = strs.length; int [][][] d = new int[l + 1][m + 1][n + 1]; for (int i = 0; i <= l; i ++){ int [] nums = new int[]{0,0}; if (i > 0){ nums = countZeroOnes(strs[i - 1]); } for (int j = 0; j <= m; j ++){ for (int k = 0; k <= n; k ++){ if (i == 0) { d[i][j][k] = 0; } else if (j >= nums[0] && k >= nums[1]){ d[i][j][k] = Math.max(d[i - 1][j][k], d[i - 1][j - nums[0]][k - nums[1]] + 1); } else { d[i][j][k] = d[i - 1][j][k]; } } } } return d[l][m][n]; } }

复杂度分析

• 时间复杂度:O(l * m * n)—— 三重循环遍历全部状态
• 空间复杂度:O(l * m * n)—— 3D dp 数组

六、Solution #4：2D DP（滚动数组压缩）

原文档指出：3D DP 保存了全部中间状态，但第 i 层只依赖第 i-1 层，因此可以先压缩为dp[2][m][n]滚动复用；进一步观察，第 i 层更新时只用到前一层的两个位置dp[i-1][j][k]与dp[i-1][j-count0][k-count1]，因此可以直接压成二维数组dp[m][n]。

dp 定义：

dp[m+1][n+1] —— 使用 m 个 0 和 n 个 1 时最多能形成的字符串数

转移方程：

dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1)

关键细节：容量维度的循环必须倒序遍历（从大到小）。因为压缩后的一维数组在更新dp[i][j]时，若正序遍历，dp[i-count0][j-count1]可能已被本层（当前字符串）更新过，导致同一个字符串被多次使用——这就不再是 0-1 背包而是完全背包了。倒序遍历保证读取到的永远是上一轮（上一字符串）的状态。这正是背包问题专题中「内层循环与外层循环不可随意颠倒」同类的背包细节。

Java

class OnesAndZeros2DDP { public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; for (String s : strs) { int[] counts = countZeroOnes(s); // 倒序遍历两个容量维度，避免重复使用当前字符串 for (int i = m; i >= counts[0]; i--) { for (int j = n; j >= counts[1]; j--) { dp[i][j] = Math.max(1 + dp[i - counts[0]][j - counts[1]], dp[i][j]); } } } return dp[m][n]; } private int[] countZeroOnes(String s) { int[] res = new int[2]; for (char ch : s.toCharArray()) { res[ch - '0']++; } return res; } }

Python3

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: l = len(strs) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1, l + 1): count0, count1 = strs[i - 1].count('0'), strs[i - 1].count('1') for i in reversed(range(count0, m + 1)): for j in reversed(range(count1, n + 1)): dp[i][j] = max(dp[i][j], 1 + dp[i - count0][j - count1]) return dp[m][n]

下图（来自仓库 assets/problems/474.ones-and-zeros-2d-dp.png）以示例 1 的输入{"10","0001","111001","1","0"}, m=5, n=3完整演示了 2D DP 表格的逐步更新过程：每处理一个字符串，满足容量约束的单元格依据转移方程递增，最终dp[5][3] = 4，与题目答案一致。

复杂度分析

• 时间复杂度:O(l * m * n)—— l 为 strs 长度，m 为 0 的数量，n 为 1 的数量
• 空间复杂度:O(m * n)—— 2D dp 数组（相比 3D 省去 l 维）

七、四种解法对比与关键点总结

关键点提炼：

1. 识别题型：求最大数量且资源有上限、每个物品只用一次 → 多维 0-1 背包；
2. 状态定义是核心：本题的二维状态(j, k)分别代表可用 0 / 1 的个数，这是整个 DP 的灵魂；
3. 转移方程：dp[i][j] = max(dp[i][j], dp[i-count0][j-count1] + 1)，取与不取二者取大；
4. 滚动数组 + 倒序遍历：空间从 O(l·m·n) 降到 O(m·n)，倒序保证每个字符串最多被选一次；
5. 面试节奏：先暴力证明理解，再逐步优化到 2D DP，展示完整的优化链条。

八、延伸阅读与相关题目

• 本仓库的动态规划讲义系统讲解了记忆化递归、状态定义、状态转移方程、滚动数组等本文依赖的全部 DP 理论；
• 416. 分割等和子集 是同仓库内另一道经典 0-1 背包题，其二维压缩为一维的推导与本题完全同构，适合对照练习；
• 322. 零钱兑换 是「完全背包」变体（硬币无限），与本题「0-1 背包」形成对比，可体会物品是否可重复使用对遍历顺序的决定性影响；
• 原文档推荐的相似练习：600. Non-negative Integers without Consecutive Ones（数位 DP 入门）与 322. Coin Change，建议分别用记忆化递归与迭代 DP 两种方式实现，并用滚动数组压缩空间。

掌握 474 题后，你会发现「两个容量维度」只是 0-1 背包的一层推广——三维、四维费用背包的解法套路完全一致：状态加维度、循环加层、滚动数组压维度，一通百通。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode