今天想聊聊题号474这道经典题一和零。它在动态规划题单里的地位很特殊名字看着像字符串处理本质上却是一道非常标准的二维费用背包问题。很多朋友刷到这道题时01背包刚上手一看数组里全是字符串又要数0又要数1直接懵了。这道题之所以值得反复做是因为它把“从一个限制维度扩展到两个限制维度”这件事讲得特别清楚做完它后面遇到多维背包、状态压缩、恰好装满这类变化基本就能举一反三。以下几个角度的拆解适合刚学完基础背包想进阶的新手也适合准备算法面试、想在短时间内建立题型判断能力的人。1. 先把题意嚼碎这题到底在求什么1.1 题干翻译成“选还是不选”的问题题目给了你一个字符串数组每个字符串里面只有两种字符0和1。同时给了两个整数m和n分别代表你最多能使用的0的个数和1的个数。现在让你从数组里挑若干个字符串要求这些字符串加起来包含的0总数不超过m包含的1总数不超过n问最多能挑几个字符串。这里有几个容易被忽略的细节。每个字符串只能选一次这是一个典型的“10背包——选或不选”的决策模型。字符串的顺序没有意义你可以任意挑选但这道题不是让你在字符串内部做子序列拼接更不是让你重新排列字符而是把每个字符串当成一个整体原样拿走。举个例子“0001”这个字符串里就有3个0和1个1你选中它就一次性消耗掉3个0和1个1的额度。m和n分别是两个独立的限制条件两者必须同时满足缺一不可。如果你做过基础的01背包题脑子里应该已经有了一个轮廓每个物品有自己的重量和价值背包容量有限求最大价值。而这道题不过是把一个重量维度换成了两个资源维度每个“物品”消耗若干0和若干1价值统一为1目标是在两个容量约束下拿到最多的“物品”。1.2 为什么排序贪心在这里行不通我第一次见到这题时第一反应是“按字符串长度排个序从短到长选”。这个思路看起来很合理字符串越短占用的0和1总量越少我应该优先选短的。但很快就能举出反例。假设m1n1000数组里有两个字符串“0”和“1”。按长度排序“0”和“1”长度一样选哪个都行但如果你先选了一个长度为10、里面全是0的字符串“0000000000”会发现0的额度直接被清空后面什么都选不了。问题出在字符串短不代表它在每个维度上都消耗得少。一个字符串可能是“0”的长度只有1也可以是“00”长度只有2但如果m很小哪怕只消耗2个0也可能直接触发上限。排序贪心只考虑了“总量”没有同时兼顾两个维度的剩余额度所以很容易被构造出来的反例击穿。还有人会想“按每个字符串的0和1总数除以长度算性价比”。这同样不行因为背包问题里局部性价比高不代表全局最优经典的01背包就不是贪心能解的。二维背包下两个维度的联合约束让贪心策略更难成立。你要么用动态规划完整地记录所有容量状态要么暴力枚举所有组合看哪个满足条件——前者高效后者只能处理数组长度极小的情况。1.3 从经典01背包到二维背包差别在哪经典01背包的dp数组是一维的比如dp[j]表示容量为j时的最大价值。这道题因为有两个容量上限dp至少是二维的dp[i][j]表示在i个0、j个1的限制下能选到的最多字符串数。多维背包本质上是把经典背包的“容量”概念泛化从一个标量变成一个向量。但这不是简单的加一个维度。二维背包会带来三个新问题第一状态空间变大时间和内存都需要重新评估第二两层容量循环的顺序和方向都有讲究一个不小心就会把“每个字符串只能选一次”变成“同一个字符串被重复选多次”第三初始化语义更容易搞混这题用“不超过”来定义容量二维数组可以直接全0初始化但如果题目改成“恰好用完”初始化就完全不同。这三点接下来会逐一展开。2. dp[i][j]怎么定义从“一个购物袋”升级到“两个购物袋”2.1 dp[i][j]到底存什么语义定死后面全顺定义dp[i][j]为在已经处理过的字符串集合中使用不超过i个0、不超过j个1的情况下最多能选出的字符串个数。注意两个关键词已经处理过、不超过。“已经处理过”意味着我们是按顺序遍历字符串数组的每处理完一个字符串dp表就反映“包含这个字符串以及之前所有字符串”的最优结果。这跟经典01背包按物品顺序一维滚动更新的逻辑一致。“不超过”则决定了初始化的方式因为任何字符串都不选也是一个合法方案字符串数量为0所以dp数组可以全部初始化为0最终答案直接取dp[m][n]。如果换一种定义比如dp[i][j]表示“恰好使用i个0、j个1”时能选到的最多字符串数初始化就不能全0了因为很多容量组合是无法恰好达成的需要用负无穷标记不可达并把dp[0][0]设为0。两种定义都能做但“不超过”语义更贴合这题也更好写。我在刷题时习惯先把这个语义明确写下来再做推导思路会清晰很多。2.2 状态转移方程的由来不选继承选则加一对于当前这个字符串假设它含有zeros个0和ones个1。面对它时只有两种决策不选它或者选它。不选它很简单dp[i][j]保持上一轮的结果。选它则要求i zeros且j ones因为只有剩余容量装得下这个字符串才有资格选。选完之后容量被消耗掉zeros的0和ones的1字符串个数加1。于是转移方程就出来了dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1)前提是i zeros且j ones。这个方程跟01背包的dp[j] max(dp[j], dp[j - weight] value)几乎一模一样只是把背包容量j换成了二元组(i, j)把价值value换成了固定值1。每次只要当前容量能放下就从“没选这个字符串”的状态加上1和“不选这个字符串”的状态比谁更大留下更优的那个。理解了这一点这题的最难部分其实已经过去了。剩下的问题是怎么把三维的状态压缩成二维以及容量循环为什么要倒序。2.3 亲手填一遍dp表一个m2,n1的小例子光看公式还是有点虚我习惯拿一个小例子手推一遍。假设strs [0, 01]m2n1。先统计两个字符串的消耗0zeros1ones001zeros1ones1初始化一个3行2列的dp表i对应0的容量0到2j对应1的容量0到1全部为0。处理0它消耗1个0和0个1。容量i必须从2往0倒着走j从1往0倒着走。当i2、j1时dp[2][1] max(dp[2][1], dp[1][1] 1)。因为dp[1][1]当前是0所以dp[2][1]变成1。同理dp[2][0]、dp[1][1]、dp[1][0]都会在条件满足时变成1。处理完这个字符串表格里只要i1的位置基本都被更新成了1。处理01它消耗1个0和1个1。注意看i2、j1这个格子。dp[2][1]当前的值为1表示只靠0最多选1个。现在考虑选01那么需要从状态dp[1][0]转移过来因为2减去1个0等于11减去1个1等于0。dp[1][0]在上一轮已经被更新为1说明只用1个0、0个1的额度时可以选到1个字符串也就是0。那再选上01总数就是2。于是dp[2][1]被更新为max(1, 1 1) 2。最终答案dp[2][1]2确实可以同时选0和01。这个手推过程非常值得自己走一遍。它能让你直观看到dp表中每个格子是如何被旧状态激活的也好理解“选当前字符串”本质上是在“以前选过的组合”基础上累加。3. 代码实现与空间压缩三维dp到二维dp的完整演进3.1 先写三维版本最直白但最容易超内存的写法如果完全照搬背包的思路最容易想到的是三维dpdp[k][i][j]表示在前k个字符串中使用不超过i个0、j个1时能选到的最多字符串数。外层循环遍历字符串中间和内部循环遍历两个容量维度。def findMaxForm(strs, m, n): k len(strs) dp [[[0] * (n 1) for _ in range(m 1)] for _ in range(k 1)] for idx in range(1, k 1): s strs[idx - 1] zeros s.count(0) ones len(s) - zeros for i in range(m 1): for j in range(n 1): dp[idx][i][j] dp[idx - 1][i][j] if i zeros and j ones: dp[idx][i][j] max( dp[idx][i][j], dp[idx - 1][i - zeros][j - ones] 1 ) return dp[k][m][n]这个版本最符合直觉但空间复杂度是O(k * m * n)。当字符串数量k、m、n都达到几百时内存会很快吃紧。绝大多数题解和面试官期望的版本都是把第一维“已经处理的字符串数量”压缩掉。压缩的思想基于一个事实第k层的状态只依赖第k-1层前面的层不再需要。所以我们只需要保留一个二维dp表在每个字符串到来时原地更新它。3.2 空间压缩原理为什么内层容量必须倒序遍历压缩后的核心代码就两行内层循环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)这里最关键的是两层循环都必须从大到小遍历。原因和经典01背包的“倒序更新”一样为了确保dp[i - zeros][j - ones]是上一轮的结果也就是“还没考虑当前字符串”时的最优值。如果正序更新小的容量会先被当前字符串更新然后大的容量在计算时又用了这个已经被污染的值就相当于当前字符串被使用了多次。我们拿一个极端的例子看。假如当前字符串是0zeros1ones0。如果容量i正序遍历先更新dp[1][0] max(dp[1][0], dp[0][0] 1) 1接着更新dp[2][0] max(dp[2][0], dp[1][0] 1) 2这不就把同一个0选了两次吗倒序遍历时dp[2][0]会先基于还没被本轮污染的dp[1][0]来更新这个dp[1][0]是上一轮的旧值恰好保证了每个字符串最多被选一次。二维压缩后两个维度都需要倒序漏掉任何一个都会导致答案偏大。这是这道题最隐蔽、也最常考的细节。3.3 参考实现Python与C两个版本直接抄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]C版本逻辑相同int findMaxForm(vectorstring strs, int m, int n) { vectorvectorint dp(m 1, vectorint(n 1, 0)); for (const string s : strs) { int zeros 0; for (char c : s) { if (c 0) zeros; } int ones s.size() - zeros; for (int i m; i zeros; i--) { for (int j n; j ones; j--) { dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1); } } } return dp[m][n]; }做一个小优化统计字符串时只数一遍01的个数用总长度减去0的个数这样比调用两次计数函数更快。时间复杂度和空间复杂度方面整个过程需要遍历每个字符串每个字符串还要更新整个m乘n的dp表所以时间复杂度为O(len(strs) * m * n)空间复杂度为O(m * n)。3.4 边界条件处理m或n为0、字符串超额等情况m或n为0时代码依然能正确执行。假设m0n5那么任何包含0的字符串都无法被选中因为它们会消耗0的额度。但有一种特殊情况字符串全由1组成比如111当n足够时可以选。代码里的循环条件i从m到zeros-1也就是从0到-1区间为空所以所有包含0的字符串都不会进入更新逻辑。而如果字符串的ones也恰好为0比如空字符串——但题目限制字符串非空且只含0/1所以不存在这种情况不用额外处理。另一个容易忽视的情况是某个字符串的zeros大于m或者ones大于n。这意味着它无论何时都无法被选中因为在任何容量状态下它都会突破至少一个上限。这时候内层循环根本不会执行相当于自动跳过了这个字符串。代码不需要显式判断但如果你在预处理阶段手动过滤掉这些字符串可以减少无意义的循环次数。前提是过滤时注意不能改变原数组顺序因为这是一个组合选择问题顺序无关紧要过滤是安全的。还有一点dp表为什么要开成(m1)行、(n1)列因为i要能取到mj要能取到n所以数组长度必须在最大值基础上加1。很多新手写成m行n列然后发现最后访问dp[m][n]直接越界这个问题在笔试环境里会造成运行时错误非常不值。4. 只刷这一题不够识别二维背包的套路与5个变式4.1 面试中识别二维背包的三个信号在面试现场怎么快速判断一道题是二维背包而不是别的我一般看三个信号。第一题目给你一个“物品集合”每个物品可以选择或丢弃不存在必须按顺序拼接、排列之类的要求。第二每个物品至少有两个独立的资源消耗而且每个资源都有对应的总量上限。第三最终目标是最大化某个数值比如数量、总价值而且这个数值是每个物品贡献的累加。只要同时满足这三个条件基本可以确定用二维背包的框架。拿这道题验证字符串数组是物品集合每个字符串消耗一定数量的0和1m和n是两个上限目标是最大化选出字符串的数量。三个信号全部命中。有时候题目会把“消耗”包装得比较隐蔽比如“一个任务需要x个工人和y天完成”“一个项目占用内存和CPU时间”本质都是一样的。你要做的就是把每个物品的两个消耗值提取出来然后套用dp[i][j]的模型。4.2 从“一和零”延伸出的5个变式变式一把两个限制维度替换成“总长度和其他字符数量”。比如给定一批字符串限制总字符数不超过L、字母a的数量不超过K求最多选几个。状态定义、转移方程、循环顺序完全一致只是统计的内容变了。变式二每个物品的价值不再是固定的1而是带有一个权重数组希望在容量限制下最大化总价值。转移方程从dp[i - zeros][j - ones] 1变成dp[i - zeros][j - ones] weight[idx]思路没有变化。变式三要求“恰好用完m个0和n个1”而不是“不超过”。初始化需要把所有状态设为负无穷dp[0][0]0转移时还要判断来源状态是否可达。这个变式能帮助你真正理解“不超过”和“恰好”两种语义的差异。变式四每个物品可以重复使用多次那就是二维完全背包。实现上只需把两层容量循环改为正序遍历因为正序允许同一个物品被多次纳入。对比这道题的双倒序正好能加深对循环方向的理解。变式五再增加一个限制维度变成三维背包。比如每个任务还消耗一定内存限制条件增加一个pdp就变成三维数组dp[i][j][k]转移需要三个维度同时满足。时间和空间复杂度相应增加如果规模大还需要考虑剪枝或换状态定义。4.3 进阶建议多维背包该往哪个方向练学完这道题我建议不要急着看更多花哨的背包题型先做两类训练。第一类是把同一道题用三维dp、二维dp各写一遍再尝试把容量循环方向故意改错观察结果变化这样能彻底搞懂滚动数组的机理。第二类是找几个“恰好装满”的二维背包变式因为这类题目对初始化和状态可达性的要求更高能倒逼你理解dp表的每一个状态到底代表什么。如果还想更进一步可以思考如何优化维度特别大的情况。比如某个资源上限非常大而物品数量很小直接把上限作为dp维度就会超时这时候可能需要换一种状态定义比如dp[t][j]表示“已经选了t个物品”时另一个维度的最小消耗。这种换维度思想在省选和高级算法题里经常出现掌握这个思路比多刷十道模板题管用。5. 高频报错与排查实录一张对照表教你快速避坑5.1 典型错误对照表现象、原因、解法我把自己和身边人反复踩过的坑整理成了一张表刷这题时可以直接对照排查。现象可能原因解决思路答案偏大内层容量循环用了正序遍历同一个字符串被重复选择两个容量循环必须从大到小答案偏小统计1数量时出错或循环边界漏了ones-1导致部分容量没更新统一用len(s) - zeros统计1检查range终点运行时数组越界dp表开成了m行n列却访问dp[m][n]开成(m1)行、(n1)列结果始终为0使用“恰好”语义的初始化但没有负无穷标记明确是“不超过”语义并全0初始化样例能过但提交就错没有考虑zeros或ones超过m/n的大量字符串但这类字符串只是不参与更新不会影响结果如果用了错误的预处理可能会改变结果过滤时只跳过不可选字符串不要改变剩余的物品集合内存超限使用了三维dp且没有压缩压缩成二维dp或者用滚动数组5.2 调试技巧小样例手推 暴力枚举验证程序写好之后光看逻辑很难发现隐藏问题。我的做法是构造一个小规模样例m和n都取2或3字符串数量不超过4个然后手推一遍dp表。手推过程能帮你确认每一步的转移是否符合预期尤其是倒序更新时旧值是否被正确使用。更强的验证方式是写一个暴力枚举函数。在字符串数量很小比如不超过10时枚举所有子集检查每个子集的0和1总数是否满足限制记录最大长度再和dp结果对比。这个办法虽然只适用于小数据但能有效证明你的dp转移没有原则性错误。我写代码时常用这个办法做自测随机生成字符串数组跑几十次对比暴力结果和dp结果全对就说明核心逻辑没毛病。5.3 关于统计、遍历顺序与效率的三个小经验统计每个字符串的0和1数量时记住一个原则能少遍历就少遍历。很多暴力写法会在内层循环里反复调用计数函数导致时间浪费。正确做法是在外层循环拿到字符串后立刻统计一次然后存到局部变量里。字符串数量很多时这个细节能让代码快不少。遍历顺序方面我试过把m和n两个循环的位置调换结果完全一样所以两个维度谁外层谁内层不影响正确性。但从可读性角度来说习惯把“0的容量”放外层对应dp[i][j]中i在前不容易搞混。还有一个实战小技巧如果你在笔试环境里时间紧张可以先写三维dp版本确认答案正确后再压缩成二维。三维版本虽然内存大但不容易在循环方向上出错一旦发现结果不对排查起来也比二维版本直观。先用三维拿基础分再优化到二维拿高分这不是什么丢人的策略反而是一种务实的做法。这道题我前后刷过好几遍每次都有新体会。第一次卡在空间压缩上总担心二维数组会丢掉之前的状态后来亲手推了一次dp表才真正明白max操作天然保留了“不选当前字符串”的旧状态。面试中如果遇到类似的二维背包题我建议先别急着写代码拿出纸笔把每个物品的消耗列出来再默写一遍“不选/选”的决策和倒序更新逻辑。这道题最好的刷法是把三维版本、二维版本各写一遍把循环方向改错观察一下结果再拿暴力枚举验证一遍。做完这些后面遇到再复杂的背包变式你也只是往这个框架里加维度、改初始化而已。