1. 问题背景与题目解析今天我们来拆解LeetCode第474题一和零这是一道中等难度的动态规划问题。题目描述如下给定一个字符串数组strs和两个整数m和n你需要找出并返回strs的最大子集的大小该子集中最多有m个0和n个1。这道题看似简单实则暗藏玄机。它考察的是动态规划中的多维背包问题变种需要我们在有限的0和1资源下选择尽可能多的字符串。这类问题在实际开发中其实很常见比如资源分配问题CPU和内存双重限制广告投放优化预算和点击率双重指标云资源调度计算和存储双重约束2. 解题思路分析2.1 问题转化与建模首先我们需要明确几个关键点每个字符串都有其成本包含的0和1的数量我们有双重限制m个0和n个1目标是最大化选择的字符串数量这实际上是一个典型的二维背包问题背包容量m个0和n个1物品字符串数组中的每个字符串物品重量字符串中0和1的数量物品价值每个字符串的价值可以视为1因为我们只关心数量2.2 动态规划状态定义我们需要定义一个三维DP数组dp[k][i][j]表示考虑前k个字符串时使用i个0和j个1能组成的最大子集大小为了优化空间复杂度可以降维处理dp[i][j]使用i个0和j个1能组成的最大子集大小2.3 状态转移方程对于每个字符串我们需要统计其中0和1的数量zeros和ones更新DP数组for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1)这个转移方程的意思是如果我们选择当前字符串那么剩余可用的0和1数量就会减少同时子集大小增加1。3. 完整代码实现3.1 Python解法def findMaxForm(strs, m, n): dp [[0] * (n 1) for _ in range(m 1)] for s in strs: zeros s.count(0) ones len(s) - zeros for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1) return dp[m][n]3.2 复杂度分析时间复杂度O(L * m * n)其中L是字符串数组的长度空间复杂度O(m * n)4. 关键优化点与注意事项4.1 预处理字符串计数在循环开始前我们可以先预处理每个字符串的0和1数量避免在DP循环中重复计算counts [(s.count(0), len(s) - s.count(0)) for s in strs]4.2 遍历顺序的重要性注意DP数组的遍历必须是从后往前m→0n→0这是为了避免重复计算。如果从前向后遍历同一个字符串可能会被多次使用。4.3 边界条件处理当m0且n0时只能选择空字符串当字符串数组为空时返回0当没有任何字符串满足条件时返回05. 实际应用场景扩展这道题的解法可以应用于很多实际场景云资源调度在有限的CPU和内存资源下选择最多数量的任务来执行广告投放优化在预算和点击率的双重限制下选择最多数量的广告投资组合优化在风险和收益的双重约束下选择最多数量的投资标的6. 常见错误与调试技巧6.1 错误示例1正向遍历DP数组# 错误写法 for i in range(zeros, m 1): for j in range(ones, n 1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1)这样会导致同一个字符串被多次使用结果偏大。6.2 错误示例2忽略字符串预处理如果在DP循环中每次都计算0和1的数量时间复杂度会大幅增加# 低效写法 for s in strs: for i in range(m, s.count(0) - 1, -1): for j in range(n, (len(s) - s.count(0)) - 1, -1): ...6.3 调试技巧可以在关键位置添加打印语句观察DP数组的变化print(fProcessing string: {s}, zeros: {zeros}, ones: {ones}) for row in dp: print(row) print(-----)7. 进阶思考与变种问题7.1 如果要求具体选择的字符串而不仅是数量我们需要额外维护一个选择路径的数组记录每个状态下的字符串选择情况。7.2 如果0和1的限制是恰好而不是最多需要修改初始条件dp[0][0] 0其他初始为-∞。7.3 如果每个字符串有不同的价值修改状态转移方程将1改为value[k]。8. 性能优化实战对于大规模数据可以考虑以下优化提前终止当dp[m][n]达到可能的最大值所有字符串都被选中时提前终止剪枝跳过0和1数量都大于当前剩余资源的字符串并行计算将字符串分组并行处理需要修改DP实现优化后的代码框架def findMaxForm(strs, m, n): counts [(s.count(0), len(s)-s.count(0)) for s in strs] counts [c for c in counts if c[0] m and c[1] n] # 剪枝 dp [[0]*(n1) for _ in range(m1)] for zeros, ones in counts: for i in range(m, zeros-1, -1): for j in range(n, ones-1, -1): if dp[i-zeros][j-ones] 1 dp[i][j]: dp[i][j] dp[i-zeros][j-ones] 1 if dp[i][j] len(counts): # 提前终止 return dp[i][j] return dp[m][n]9. 测试用例设计好的测试用例应该覆盖各种边界情况test_cases [ ([10,0001,111001,1,0], 5, 3, 4), # 常规情况 ([10,0,1], 1, 1, 2), # 刚好满足限制 ([111,1000,1000,1000], 9, 3, 3), # 多个相同字符串 ([00,000], 1, 10, 0), # 无法满足0的限制 ([11,111], 10, 1, 0), # 无法满足1的限制 ([], 5, 3, 0), # 空输入 ([0,0,0,0], 0, 10, 0), # m0的特殊情况 ([1,1,1,1], 10, 0, 0) # n0的特殊情况 ]10. 与其他背包问题的对比为了更好理解这道题的特点我们将其与经典背包问题对比特征经典0-1背包本题多维背包限制条件数量单重重量双重0和1数量目标最大价值最大数量物品价值各不相同统一为1状态维度一维二维这种对比可以帮助我们更好地理解背包问题的各种变种。 LeetCode 474题解析：动态规划解决多维背包问题
1. 问题背景与题目解析今天我们来拆解LeetCode第474题一和零这是一道中等难度的动态规划问题。题目描述如下给定一个字符串数组strs和两个整数m和n你需要找出并返回strs的最大子集的大小该子集中最多有m个0和n个1。这道题看似简单实则暗藏玄机。它考察的是动态规划中的多维背包问题变种需要我们在有限的0和1资源下选择尽可能多的字符串。这类问题在实际开发中其实很常见比如资源分配问题CPU和内存双重限制广告投放优化预算和点击率双重指标云资源调度计算和存储双重约束2. 解题思路分析2.1 问题转化与建模首先我们需要明确几个关键点每个字符串都有其成本包含的0和1的数量我们有双重限制m个0和n个1目标是最大化选择的字符串数量这实际上是一个典型的二维背包问题背包容量m个0和n个1物品字符串数组中的每个字符串物品重量字符串中0和1的数量物品价值每个字符串的价值可以视为1因为我们只关心数量2.2 动态规划状态定义我们需要定义一个三维DP数组dp[k][i][j]表示考虑前k个字符串时使用i个0和j个1能组成的最大子集大小为了优化空间复杂度可以降维处理dp[i][j]使用i个0和j个1能组成的最大子集大小2.3 状态转移方程对于每个字符串我们需要统计其中0和1的数量zeros和ones更新DP数组for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1)这个转移方程的意思是如果我们选择当前字符串那么剩余可用的0和1数量就会减少同时子集大小增加1。3. 完整代码实现3.1 Python解法def findMaxForm(strs, m, n): dp [[0] * (n 1) for _ in range(m 1)] for s in strs: zeros s.count(0) ones len(s) - zeros for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1) return dp[m][n]3.2 复杂度分析时间复杂度O(L * m * n)其中L是字符串数组的长度空间复杂度O(m * n)4. 关键优化点与注意事项4.1 预处理字符串计数在循环开始前我们可以先预处理每个字符串的0和1数量避免在DP循环中重复计算counts [(s.count(0), len(s) - s.count(0)) for s in strs]4.2 遍历顺序的重要性注意DP数组的遍历必须是从后往前m→0n→0这是为了避免重复计算。如果从前向后遍历同一个字符串可能会被多次使用。4.3 边界条件处理当m0且n0时只能选择空字符串当字符串数组为空时返回0当没有任何字符串满足条件时返回05. 实际应用场景扩展这道题的解法可以应用于很多实际场景云资源调度在有限的CPU和内存资源下选择最多数量的任务来执行广告投放优化在预算和点击率的双重限制下选择最多数量的广告投资组合优化在风险和收益的双重约束下选择最多数量的投资标的6. 常见错误与调试技巧6.1 错误示例1正向遍历DP数组# 错误写法 for i in range(zeros, m 1): for j in range(ones, n 1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1)这样会导致同一个字符串被多次使用结果偏大。6.2 错误示例2忽略字符串预处理如果在DP循环中每次都计算0和1的数量时间复杂度会大幅增加# 低效写法 for s in strs: for i in range(m, s.count(0) - 1, -1): for j in range(n, (len(s) - s.count(0)) - 1, -1): ...6.3 调试技巧可以在关键位置添加打印语句观察DP数组的变化print(fProcessing string: {s}, zeros: {zeros}, ones: {ones}) for row in dp: print(row) print(-----)7. 进阶思考与变种问题7.1 如果要求具体选择的字符串而不仅是数量我们需要额外维护一个选择路径的数组记录每个状态下的字符串选择情况。7.2 如果0和1的限制是恰好而不是最多需要修改初始条件dp[0][0] 0其他初始为-∞。7.3 如果每个字符串有不同的价值修改状态转移方程将1改为value[k]。8. 性能优化实战对于大规模数据可以考虑以下优化提前终止当dp[m][n]达到可能的最大值所有字符串都被选中时提前终止剪枝跳过0和1数量都大于当前剩余资源的字符串并行计算将字符串分组并行处理需要修改DP实现优化后的代码框架def findMaxForm(strs, m, n): counts [(s.count(0), len(s)-s.count(0)) for s in strs] counts [c for c in counts if c[0] m and c[1] n] # 剪枝 dp [[0]*(n1) for _ in range(m1)] for zeros, ones in counts: for i in range(m, zeros-1, -1): for j in range(n, ones-1, -1): if dp[i-zeros][j-ones] 1 dp[i][j]: dp[i][j] dp[i-zeros][j-ones] 1 if dp[i][j] len(counts): # 提前终止 return dp[i][j] return dp[m][n]9. 测试用例设计好的测试用例应该覆盖各种边界情况test_cases [ ([10,0001,111001,1,0], 5, 3, 4), # 常规情况 ([10,0,1], 1, 1, 2), # 刚好满足限制 ([111,1000,1000,1000], 9, 3, 3), # 多个相同字符串 ([00,000], 1, 10, 0), # 无法满足0的限制 ([11,111], 10, 1, 0), # 无法满足1的限制 ([], 5, 3, 0), # 空输入 ([0,0,0,0], 0, 10, 0), # m0的特殊情况 ([1,1,1,1], 10, 0, 0) # n0的特殊情况 ]10. 与其他背包问题的对比为了更好理解这道题的特点我们将其与经典背包问题对比特征经典0-1背包本题多维背包限制条件数量单重重量双重0和1数量目标最大价值最大数量物品价值各不相同统一为1状态维度一维二维这种对比可以帮助我们更好地理解背包问题的各种变种。