1. 问题背景与题目解析LeetCode 474题一和零是一个经典的动态规划问题属于中等难度。题目描述如下给定一个字符串数组strs和两个整数m和n你需要找到并返回strs的最大子集的大小该子集中最多有m个0和n个1。每个字符串中的字符只能是0或1。这个问题的核心在于如何在有限的0和1资源下选择最多的字符串组合。它实际上是经典的0-1背包问题的变种只不过这里的背包容量有两个维度0的数量和1的数量。2. 解题思路分析2.1 问题转化首先我们需要将这个问题转化为更易理解的模型。每个字符串可以看作是一个物品它有两个属性0的个数重量11的个数重量2我们的目标是选择尽可能多的物品使得所有选中物品的0的总数 ≤ m所有选中物品的1的总数 ≤ n这明显是一个二维费用的背包问题。2.2 动态规划定义我们定义一个三维动态规划数组dp其中dp[i][j][k]表示在前i个字符串中使用最多j个0和k个1能够组成的最大子集的大小状态转移方程为如果不选第i个字符串dp[i][j][k] dp[i-1][j][k]如果选第i个字符串dp[i][j][k] dp[i-1][j-zero][k-one] 1 其中zero和one分别是第i个字符串中0和1的数量最终结果是dp[strs.length][m][n]2.3 空间优化由于每次状态转移只依赖于前一行我们可以将三维数组优化为二维数组节省空间dp[j][k]表示使用最多j个0和k个1能够组成的最大子集的大小此时需要从后向前更新dp数组避免覆盖还未使用的数据。3. 详细代码实现3.1 预处理函数首先我们需要一个辅助函数来计算每个字符串中0和1的数量def count_zero_and_one(s): zero s.count(0) one len(s) - zero return zero, one3.2 动态规划解法完整实现代码如下def findMaxForm(strs, m, n): dp [[0] * (n 1) for _ in range(m 1)] for s in strs: zero, one count_zero_and_one(s) # 从后向前遍历避免重复计算 for i in range(m, zero - 1, -1): for j in range(n, one - 1, -1): dp[i][j] max(dp[i][j], dp[i - zero][j - one] 1) return dp[m][n]3.3 复杂度分析时间复杂度O(l * m * n)其中l是字符串数组的长度空间复杂度O(m * n)使用二维数组存储状态4. 实际应用与变种4.1 实际应用场景这个问题虽然看起来抽象但实际上有很多现实应用资源分配问题在有限的两种资源下选择最优的项目组合广告投放优化在预算和展示次数限制下选择最优广告组合投资组合选择在风险和收益的双重限制下选择投资组合4.2 问题变种这个问题可以有多种变体每个字符串有不同的价值求最大价值而非最大数量增加第三种限制条件如字符串长度需要输出具体的字符串组合而不仅仅是数量5. 常见错误与调试技巧5.1 常见错误初始化错误dp数组大小应该是(m1)×(n1)不是m×n遍历顺序错误必须从后向前更新dp数组否则会重复计算边界条件处理当m或n为0时的特殊情况需要处理5.2 调试技巧打印中间状态在循环中打印dp数组观察状态变化小规模测试先用小的测试用例验证代码正确性对比暴力解对于小规模数据可以对比暴力解的结果6. 性能优化建议预处理所有字符串的0和1计数避免重复计算根据实际情况可以先对字符串进行排序如按长度可能有助于提前剪枝对于特别大的m和n可以考虑记忆化搜索而非动态规划7. 扩展思考这个问题展示了动态规划的灵活性。传统的背包问题只有一个容量限制而这个问题有两个体现了动态规划处理多维约束的能力。理解这个问题的解法有助于解决更复杂的资源分配问题。在实际面试中面试官可能会追问如何修改代码以记录选择的字符串如果字符串可以重复选择如何修改算法如何优化算法以处理极大m和n的情况掌握这类问题的核心在于理解状态定义和转移方程的本质而不是死记硬背模板。建议多练习类似的二维费用背包问题加深理解。