LeetCode 474. 一和零
目录
题目描述
✅ 474. 一和零
题意分析
给一组只含
'0'和'1'的字符串strs，再给两个上限m和n，要从strs里挑出一个子集，使得子集内所有字符串加起来用掉的'0'不超过m个、'1'不超过n个，问这个子集最多能有几个字符串。注意问的是个数，不是长度，也不是要求恰好用完。
两个信号很直白。第一，每个字符串要么整个选、要么整个不选，不能拆开用一半，这是典型的「每个物品选或不选」结构。第二，约束不是一个而是两个，且两个约束互相独立、都必须同时满足——一个字符串同时消耗两种不同的资源。这两点合起来决定了状态里必须同时记住「还剩多少个 0 的额度」和「还剩多少个 1 的额度」，一维状态是不够的。
还有一点值得注意：题目只关心 0 和 1 各有多少个，字符串内部的顺序完全无关。所以每个字符串可以提前压缩成一对数字
(zeros, ones)，原始字符串本身在决策阶段就没用了。
数据范围里
m、n都不超过 100，strs长度不超过 600，这个规模允许对每个字符串把 $101 \times 101$ 的状态表整体刷一遍。
边界：
strs可能为空，答案是 0；m或n可能是 0，此时只能选那些完全不含对应字符的字符串；某个字符串本身就超额（比如"111"而n = 2），它永远进不了任何合法子集。
解法：二维 0-1 背包
核心思路
暴力做法是枚举
strs的全部子集，逐个统计 0 和 1 的总数再取合法子集的最大规模，复杂度 $O(2^L \cdot L)$，L = 600时完全不可能。瓶颈在于大量子集其实是「等价」的：两个不同子集，只要用掉的 0 数和 1 数相同，它们对后续决策的影响就完全一样，剩下唯一有意义的区别就是各自已经选了几个字符串。既然如此，就不该按子集枚举，而该按「用掉多少 0、用掉多少 1」来归并。
于是定义状态：
dp[i][j]表示在只允许使用不超过i个'0'和不超过j个'1'的前提下，从已经考虑过的那些字符串里最多能选出的字符串个数。「已经考虑过」这个限定很关键——dp表是随着外层遍历字符串而逐轮演进的，第k轮结束时表里存的是「只用前k个字符串」的答案。
转移就是对当前字符串的两种决策取较大者：不选它，
dp[i][j]保持不变；选它，则要先腾出zeros个 0 和ones个 1 的额度，剩下的额度交给前面的字符串去填，即dp[i - zeros][j - ones] + 1。写成dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)。
状态定义里的「不超过」而非「恰好」是个刻意选择，它带来两个好处：
dp全部初始化为 0 就天然合法（一个字符串都不选永远可行），并且答案直接取dp[m][n]而不需要在末行末列里再扫一遍最大值。
最后是滚动数组的正确性。这里把「第
k个字符串」这一维压掉了，转移读的dp[i - zeros][j - ones]必须是上一轮的值（还没考虑当前字符串），才符合「每个字符串只能选一次」。由于zeros、ones都非负，被读的格子下标不大于被写的格子，所以只要两层容量循环都从大往小走，被读时它就还没在本轮被覆盖过。这就是倒序枚举的全部理由，也是 0-1 背包与完全背包在代码上唯一的差别。
解题步骤
- 开
(m + 1) × (n + 1)的二维数组dp，全部初始化为 0。多出来的那一行一列对应容量为 0 的情形，有了它转移时就不必对i - zeros == 0之类的下标做特判。初值 0 表示「一个都不选」，这是任何容量下都成立的合法解，所以它既是合法初值也是下界。- 外层遍历每个字符串：外层必须是物品维、内层才是容量维。反过来写会让同一个容量格在不同物品间来回跳，破坏「逐个物品扩展」的语义。
- 统计当前字符串的
zeros与ones：把字符串压缩成两个数字，后续转移只依赖这两个量。统计放在容量双循环之外，避免在 $O(mn)$ 次转移里重复扫描字符串。i从m递减到zeros，j从n递减到ones：递减是为了保证读到的是上一轮的值；下界取zeros/ones是因为容量不足时这个字符串根本放不下，dp[i][j]保持上一轮的值即可，顺便也避免了负下标。- 转移
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)：等号右边的dp[i][j]代表「不选」，另一项代表「选」，取大者。这里用max而不是直接赋值，因为「不选」有时才是更优解。- 返回
dp[m][n]：状态定义是「不超过」，所以容量最大的那一格就是全局最优，不需要再遍历取最大值。
以
strs = ["10", "0001", "1", "0"]、m = 3、n = 2走一遍（答案应为 3，例如选"10"、"1"、"0"）。为了看得清楚，下面只列出每轮结束后发生变化的格子，格子写作dp[i][j]。
初始：整张表全为 0。
第一轮，
"10"的(zeros, ones) = (1, 1)。i从 3 降到 1，j从 2 降到 1，每格由dp[i-1][j-1] + 1 = 0 + 1 = 1更新。结果是所有满足i ≥ 1 且 j ≥ 1的格子都变成 1，即dp[1][1] = dp[1][2] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = 1。此时dp[3][2] = 1。
第二轮，
"0001"的(zeros, ones) = (3, 1)。只有i = 3满足条件，j取 2、1。dp[3][2] = max(1, dp[0][1] + 1) = max(1, 1) = 1，dp[3][1] = max(1, dp[0][0] + 1) = 1。这一轮实际没有提升——因为选了它就用光了三个 0，剩下的额度装不下第二个字符串，和只选"10"打平。
第三轮，
"1"的(zeros, ones) = (0, 1)。i从 3 降到 0，j从 2 降到 1。关键格dp[3][2] = max(1, dp[3][1] + 1)；注意j = 2先于j = 1被处理，所以此刻dp[3][1]仍是上一轮的 1，得dp[3][2] = 2（对应选"10"和"1"）。随后dp[3][1] = max(1, dp[3][0] + 1) = 1。倒序的作用在这里显形：若正序处理，dp[3][1]会先被更新，dp[3][2]就可能读到本轮的值，等于把"1"用了两次。
补充一点第三轮的细节：
i = 2时同样有dp[2][2] = max(1, dp[2][1] + 1) = 2，对应用 2 个 0 额度、2 个 1 额度选出"10"和"1"。
第四轮，
"0"的(zeros, ones) = (1, 0)。关键格dp[3][2] = max(2, dp[2][2] + 1) = max(2, 3) = 3，对应选"10"、"1"、"0"，恰好用掉 2 个 0 和 2 个 1，在m = 3、n = 2之内。
遍历结束，返回
dp[3][2] = 3。
代码实现
class Solution {
// dp[i][j] 表示在最多使用 i 个 0、j 个 1 时，最多能选择多少个字符串。
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {
int zeros = 0;
int ones = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}
func findMaxForm(strs []string, m int, n int) int {
// dp[i][j] 表示在最多使用 i 个 0、j 个 1 时，最多能选择多少个字符串。
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for _, s := range strs {
zeros := 0
ones := 0
for i := 0; i < len(s); i++ {
if s[i] == '0' {
zeros++
} else {
ones++
}
}
for i := m; i >= zeros; i-- {
for j := n; j >= ones; j-- {
val := dp[i-zeros][j-ones] + 1
if val > dp[i][j] {
dp[i][j] = val
}
}
}
}
return dp[m][n]
}
复杂度分析
- 时间复杂度：$O(T + L \cdot m \cdot n)$，其中
L是字符串个数、T是所有字符串的总长度。凭什么：统计每个字符串的 0、1 个数合计扫过全部字符，贡献 $O(T)$；随后每个字符串都要把 $(m+1) \times (n+1)$ 的状态表刷一遍，每格是常数次比较赋值，贡献 $O(L \cdot m \cdot n)$。- 空间复杂度：$O(mn)$。凭什么：物品维已被滚动数组压掉，只保留一张 $(m+1) \times (n+1)$ 的表，与字符串条数无关；
zeros、ones等是常数级变量。
关键点总结
- 多维背包的本质是「一个物品同时消耗多种资源」，状态维数等于资源种类数，转移式的形状和一维背包完全一样，只是下标多减了一项——认出这一点，879 这类三维变体也能直接推广。
- 状态定义写「不超过」而不是「恰好」，能让初值全 0 天然合法、答案直接落在
dp[m][n]，省掉初始化的-∞和末尾的取最值扫描。面试时主动说明这个取舍是加分点。- 0-1 背包压维后必须倒序枚举容量，理由是「保证读到的是上一轮的值」；完全背包正序，理由是「就是要读本轮的值以允许重复选」。把理由讲成这一句话，两类题就不会记混。
- 与顺序无关的输入应尽早压缩成决策真正需要的特征（这里是把字符串压成
(zeros, ones)），既降复杂度也让转移式更干净。- 容量循环的下界取
zeros/ones而非 0，既是性能优化也是天然的越界防护，比在循环体里写if判断更简洁。
易错点总结
- 两层容量循环写成正序递增：
strs = ["1"]、m = 0、n = 3时dp[1]更新后dp[2]会读到本轮的dp[1]，把同一个"1"反复计入，返回 3 而不是 1。- 只把外层
i写成倒序、内层j写成正序：strs = ["01"]、m = 3、n = 3时dp[3][3]会经由本轮已更新的dp[2][2]累加，同一字符串被用两次，答案偏大。- 物品维和容量维的循环嵌套写反（外层容量、内层物品）：
strs = ["10","0001","1","0"]这类用例下，同一个容量格会在一次内层循环里被所有物品连续更新，等价于允许重复选取，结果偏大。dp初始化成-1或Integer.MIN_VALUE：改成「恰好装满」语义却没同步改返回值，strs = ["10"]、m = 3、n = 3时dp[3][3]仍是负数，返回负值。- 忘记
Math.max，直接写dp[i][j] = dp[i - zeros][j - ones] + 1：strs = ["0","1"]、m = 1、n = 1时第二轮会把已经算好的更优解覆盖成更差的值，返回 1 而不是 2。- 容量循环下界写成 0 而不做越界保护：
strs = ["0001"]、m = 3时i = 0会访问dp[-3][...]，Java 抛数组越界异常，Go 触发 panic。- 把
zeros、ones的统计放进容量双循环内部：功能正确但每轮多做 $O(mn)$ 次字符串扫描，L = 600、m = n = 100时直接超时。- 误以为要在整张表里取最大值返回：
strs = ["0"]、m = 3、n = 3时确实无害，但一旦有人把状态改成「恰好」语义又保留dp[m][n]的返回方式，m用不满的用例就会返回 0。- 统计时用
s.length() - zeros推ones却没考虑非 0/1 字符：本题输入保证只有 0 和 1，但把这个假设写死在代码里而不显式统计，迁移到含其他字符的变体时会静默给出错误的容量消耗。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 单一容量维、状态是布尔可行性而非最大个数，是本题降到一维的原型 |
| 494. 目标和 | 中等 | 先把正负号问题转化成子集和，状态存的是方案计数，转移用加法而非取最值 |
| 1049. 最后一块石头的重量 II | 中等 | 把两堆石头相消转化为「尽量接近总和一半」的一维背包，目标是最小化剩余差值 |
| 879. 盈利计划 | 困难 | 同样是双约束，但利润维是「至少达到」而非「不超过」，下标需要截断到 0 |
| 518. 零钱兑换 II | 中等 | 完全背包，物品可重复选，容量循环改为正序，正好和本题的倒序形成对照 |
| 322. 零钱兑换 | 中等 | 完全背包求最少个数，初值要设成不可达的大数，与本题初值全 0 的取舍相反 |
| LCR 101. 分割等和子集 | 简单 | 与 416 同题，可直接套用一维可行性背包 |
| LCR 102. 目标和 | 中等 | 与 494 同题，用来练习计数型背包的初值 dp[0] = 1
|