企业官网建设流程全解析

今天想聊聊题号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总量越少，我应该优先选短的。但很快就能举出反例。

假设m=1，n=1000，数组里有两个字符串：“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表：一个m=2,n=1的小例子

光看公式还是有点虚，我习惯拿一个小例子手推一遍。假设strs = ["0", "01"]，m=2，n=1。

先统计两个字符串的消耗：

• "0"：zeros=1，ones=0
• "01"：zeros=1，ones=1

初始化一个3行2列的dp表（i对应0的容量0到2，j对应1的容量0到1），全部为0。

处理"0"，它消耗1个0和0个1。容量i必须从2往0倒着走，j从1往0倒着走。当i=2、j=1时，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。处理完这个字符串，表格里只要i>=1的位置，基本都被更新成了1。

处理"01"，它消耗1个0和1个1。注意看i=2、j=1这个格子。dp[2][1]当前的值为1，表示只靠"0"最多选1个。现在考虑选"01"，那么需要从状态dp[1][0]转移过来，因为2减去1个0等于1，1减去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 先写三维版本：最直白但最容易超内存的写法

如果完全照搬背包的思路，最容易想到的是三维dp：dp[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]是上一轮的结果，也就是“还没考虑当前字符串”时的最优值。如果正序更新，小的容量会先被当前字符串更新，然后大的容量在计算时又用了这个已经被污染的值，就相当于当前字符串被使用了多次。

我们拿一个极端的例子看。假如当前字符串是"0"，zeros=1，ones=0。如果容量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(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(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]; }

做一个小优化：统计字符串时只数一遍'0'，'1'的个数用总长度减去'0'的个数，这样比调用两次计数函数更快。时间复杂度和空间复杂度方面，整个过程需要遍历每个字符串，每个字符串还要更新整个m乘n的dp表，所以时间复杂度为O(len(strs) * m * n)，空间复杂度为O(m * n)。

3.4 边界条件处理：m或n为0、字符串超额等情况

m或n为0时，代码依然能正确执行。假设m=0，n=5，那么任何包含'0'的字符串都无法被选中，因为它们会消耗0的额度。但有一种特殊情况：字符串全由'1'组成，比如"111"，当n足够时可以选。代码里的循环条件i从m到zeros-1，也就是从0到-1，区间为空，所以所有包含'0'的字符串都不会进入更新逻辑。而如果字符串的ones也恰好为0，比如空字符串——但题目限制字符串非空且只含'0'/'1'，所以不存在这种情况，不用额外处理。

另一个容易忽视的情况是某个字符串的zeros大于m，或者ones大于n。这意味着它无论何时都无法被选中，因为在任何容量状态下，它都会突破至少一个上限。这时候内层循环根本不会执行，相当于自动跳过了这个字符串。代码不需要显式判断，但如果你在预处理阶段手动过滤掉这些字符串，可以减少无意义的循环次数。前提是过滤时注意不能改变原数组顺序，因为这是一个组合选择问题，顺序无关紧要，过滤是安全的。

还有一点，dp表为什么要开成(m+1)行、(n+1)列？因为i要能取到m，j要能取到n，所以数组长度必须在最大值基础上加1。很多新手写成m行n列，然后发现最后访问dp[m][n]直接越界，这个问题在笔试环境里会造成运行时错误，非常不值。

4. 只刷这一题不够：识别二维背包的套路与5个变式

4.1 面试中识别二维背包的三个信号

在面试现场，怎么快速判断一道题是二维背包而不是别的？我一般看三个信号。第一，题目给你一个“物品集合”，每个物品可以选择或丢弃，不存在必须按顺序拼接、排列之类的要求。第二，每个物品至少有两个独立的资源消耗，而且每个资源都有对应的总量上限。第三，最终目标是最大化某个数值，比如数量、总价值，而且这个数值是每个物品贡献的累加。只要同时满足这三个条件，基本可以确定用二维背包的框架。

拿这道题验证：字符串数组是物品集合，每个字符串消耗一定数量的0和1，m和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，转移时还要判断来源状态是否可达。这个变式能帮助你真正理解“不超过”和“恰好”两种语义的差异。

变式四：每个物品可以重复使用多次，那就是二维完全背包。实现上只需把两层容量循环改为正序遍历，因为正序允许同一个物品被多次纳入。对比这道题的双倒序，正好能加深对循环方向的理解。

变式五：再增加一个限制维度，变成三维背包。比如每个任务还消耗一定内存，限制条件增加一个p，dp就变成三维数组dp[i][j][k]，转移需要三个维度同时满足。时间和空间复杂度相应增加，如果规模大，还需要考虑剪枝或换状态定义。

4.3 进阶建议：多维背包该往哪个方向练

学完这道题，我建议不要急着看更多花哨的背包题型，先做两类训练。第一类是把同一道题用三维dp、二维dp各写一遍，再尝试把容量循环方向故意改错，观察结果变化，这样能彻底搞懂滚动数组的机理。第二类是找几个“恰好装满”的二维背包变式，因为这类题目对初始化和状态可达性的要求更高，能倒逼你理解dp表的每一个状态到底代表什么。

如果还想更进一步，可以思考如何优化维度特别大的情况。比如某个资源上限非常大，而物品数量很小，直接把上限作为dp维度就会超时，这时候可能需要换一种状态定义，比如dp[t][j]表示“已经选了t个物品”时另一个维度的最小消耗。这种换维度思想在省选和高级算法题里经常出现，掌握这个思路，比多刷十道模板题管用。

5. 高频报错与排查实录：一张对照表教你快速避坑

5.1 典型错误对照表：现象、原因、解法

我把自己和身边人反复踩过的坑整理成了一张表，刷这题时可以直接对照排查。

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操作天然保留了“不选当前字符串”的旧状态。面试中如果遇到类似的二维背包题，我建议先别急着写代码，拿出纸笔把每个物品的消耗列出来，再默写一遍“不选/选”的决策和倒序更新逻辑。这道题最好的刷法是把三维版本、二维版本各写一遍，把循环方向改错观察一下结果，再拿暴力枚举验证一遍。做完这些，后面遇到再复杂的背包变式，你也只是往这个框架里加维度、改初始化而已。