题目描述
思路解析
一句话答案：LeetCode 474 一和零：把 0、1 的个数当两道容量轴的 0-1 背包。dp[i][j] 记不超过 i 个 0、j 个 1 能选的最多字符串数，每串选或不选，内层双维倒序防重复选。时间 O(L·m·n)、空间 O(m·n)。
两个预算下最多能挑几个二进制串
给一堆二进制字符串 strs，和「最多用 m 个 0、n 个 1」的总预算。每选一个串，就花掉它里面 0 和 1 的个数，问两预算都不超时最多选几个。题面例子 strs=["10","0001","1","0"]、m=3、n=3，答案是 3——全选要 5 个 0、超预算 3，丢掉最贵的 "0001"，剩 "10"、"1"、"0" 共 3 个。
为什么把所有子集试一遍数不完
最直接是把 strs 每个子集（子集＝从这堆串里任挑几个、含都不挑）列出来，逐个查是否超预算、留最多的。可 L 个串有 2^L 个子集（大 O 记号描述规模变大时操作数怎么涨），L 一大就指数级爆炸数不完，且子集大量重叠被重算。既然「某个 0、1 预算下能选几个」会被反复问到，算一次存下来复用，就是动态规划（DP，把子问题的解记下来别重算）。
为什么这是有两个容量的 0-1 背包
把它看成背包问题（背包＝把物品塞进限定容量的包）：每个串是一件物品。经典背包只有一维容量，这题一个串同时花掉 0、1 两种资源，两道容量轴一起卡，状态升到二维。定义 dp[i][j] 为「0 用不超过 i 个、1 用不超过 j 个时能选的最多字符串数」，一开始一个串都没选、整张表都是 0。每个串只有选或不选，这是 0-1 背包（每件至多选一次）。
转移式为什么两维一起扣，还得倒序
轮到含 c0 个 0、c1 个 1 的串，每格 dp[i][j] 在两条路里取大：不选它，沿用之前的 dp[i][j]；选它，就从「扣掉它消耗后」的 dp[i-c0][j-c1] 接过来加 1。合起来 dp[i][j]=max(dp[i][j], dp[i-c0][j-c1]+1)。
内层两维都要从大到小倒序遍历。这样取的 dp[i-c0][j-c1] 还是「没考虑当前串」的旧值，当前串只计一次；若某一维正序，刚更新过的格子又拿去接自己，同一个串被叠加多次，就成了每件能无限取的完全背包。
拿题面这四个串把表填出 3
四个串的消耗（0 数,1 数）："10"(1,1)、"0001"(3,1)、"1"(0,1)、"0"(1,0)。先处理 "10"，0、1 都还剩至少 1 个的格子全变成 1。再处理 "0001"，它要 3 个 0，只有 dp[3][j] 付得起，可接的 dp[0][j-1] 全是 0，选不进来。
轮到 "1"（只花 1 个 1），dp[3][3] 从 1 升到 2（接 dp[3][2]=1）。最后处理 "0"（只花 1 个 0），dp[3][3]=max(2, dp[2][3]+1)=max(2, 2+1)=3，选到的正是 "10"、"1"、"0" 这 3 个。
正序会重复选，边界又停在哪
外层扫 L 个串，每个把 (m+1)×(n+1) 的表过一遍，时间 O(L·m·n)；只留一张二维 dp 表，空间 O(m·n)。两处最容易写错：一是内层两维忘了倒序、写成正序，同一个串会被重复选、答案偏大；二是内层边界，i 只要减到 c0、j 减到 c1 就该停，预算不够付它就选不了，再减会取到负下标。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
枚举所有子集会重复计算相同容量下的最优结果。二维动态规划按两个容量上限保存这些结果。
行表示 0 的数量上限，列表示 1 的数量上限。尚未处理任何字符串，各容量下最多都只能选 0 个。
当前字符串 "10" 含 1 个 0、1 个 1。两个容量均倒序遍历，使每个字符串至多使用一次。
容量上限为 (3,3)。不选 "10" 可选 0 个；选它得到 dp[2][2]+1=0+1=1。取较大值。
比较 0 与 1，dp[3][3] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (3,2)。不选 "10" 可选 0 个；选它得到 dp[2][1]+1=0+1=1。取较大值。
比较 0 与 1，dp[3][2] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (3,1)。不选 "10" 可选 0 个；选它得到 dp[2][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[3][1] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (2,3)。不选 "10" 可选 0 个；选它得到 dp[1][2]+1=0+1=1。取较大值。
比较 0 与 1，dp[2][3] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (2,2)。不选 "10" 可选 0 个；选它得到 dp[1][1]+1=0+1=1。取较大值。
比较 0 与 1，dp[2][2] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (2,1)。不选 "10" 可选 0 个；选它得到 dp[1][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[2][1] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (1,3)。不选 "10" 可选 0 个；选它得到 dp[0][2]+1=0+1=1。取较大值。
比较 0 与 1，dp[1][3] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (1,2)。不选 "10" 可选 0 个；选它得到 dp[0][1]+1=0+1=1。取较大值。
比较 0 与 1，dp[1][2] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (1,1)。不选 "10" 可选 0 个；选它得到 dp[0][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[1][1] 更新为 1。这表示当前容量下最多能选 1 个字符串。
处理 "0001" 时，只有第 3 行的三格容量足够。选或不选都只能选 1 个，因此全表数值保持不变。
当前字符串 "1" 含 0 个 0、1 个 1。两个容量均倒序遍历，使每个字符串至多使用一次。
容量上限为 (3,3)。不选 "1" 可选 1 个；选它得到 dp[3][2]+1=1+1=2。取较大值。
比较 1 与 2，dp[3][3] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (3,2)。不选 "1" 可选 1 个；选它得到 dp[3][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[3][2] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (2,3)。不选 "1" 可选 1 个；选它得到 dp[2][2]+1=1+1=2。取较大值。
比较 1 与 2，dp[2][3] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (2,2)。不选 "1" 可选 1 个；选它得到 dp[2][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[2][2] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (1,3)。不选 "1" 可选 1 个；选它得到 dp[1][2]+1=1+1=2。取较大值。
比较 1 与 2，dp[1][3] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (1,2)。不选 "1" 可选 1 个；选它得到 dp[1][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[1][2] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (0,3)。不选 "1" 可选 0 个；选它得到 dp[0][2]+1=0+1=1。取较大值。
比较 0 与 1，dp[0][3] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (0,2)。不选 "1" 可选 0 个；选它得到 dp[0][1]+1=0+1=1。取较大值。
比较 0 与 1，dp[0][2] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (0,1)。不选 "1" 可选 0 个；选它得到 dp[0][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[0][1] 更新为 1。这表示当前容量下最多能选 1 个字符串。
当前字符串 "0" 含 1 个 0、0 个 1。两个容量均倒序遍历，使每个字符串至多使用一次。
容量上限为 (3,3)。不选 "0" 可选 2 个；选它得到 dp[2][3]+1=2+1=3。取较大值。
比较 2 与 3，dp[3][3] 更新为 3。这表示当前容量下最多能选 3 个字符串。
容量上限为 (3,2)。不选 "0" 可选 2 个；选它得到 dp[2][2]+1=2+1=3。取较大值。
比较 2 与 3，dp[3][2] 更新为 3。这表示当前容量下最多能选 3 个字符串。
容量上限为 (3,1)。不选 "0" 可选 1 个；选它得到 dp[2][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[3][1] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (3,0)。不选 "0" 可选 0 个；选它得到 dp[2][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[3][0] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (2,3)。不选 "0" 可选 2 个；选它得到 dp[1][3]+1=2+1=3。取较大值。
比较 2 与 3，dp[2][3] 更新为 3。这表示当前容量下最多能选 3 个字符串。
容量上限为 (2,2)。不选 "0" 可选 2 个；选它得到 dp[1][2]+1=2+1=3。取较大值。
比较 2 与 3，dp[2][2] 更新为 3。这表示当前容量下最多能选 3 个字符串。
容量上限为 (2,1)。不选 "0" 可选 1 个；选它得到 dp[1][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[2][1] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (2,0)。不选 "0" 可选 0 个；选它得到 dp[1][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[2][0] 更新为 1。这表示当前容量下最多能选 1 个字符串。
容量上限为 (1,1)。不选 "0" 可选 1 个；选它得到 dp[0][1]+1=1+1=2。取较大值。
比较 1 与 2，dp[1][1] 更新为 2。这表示当前容量下最多能选 2 个字符串。
容量上限为 (1,0)。不选 "0" 可选 0 个；选它得到 dp[0][0]+1=0+1=1。取较大值。
比较 0 与 1，dp[1][0] 更新为 1。这表示当前容量下最多能选 1 个字符串。
右下角 dp[3][3]=3：在「3 个 0、3 个 1」预算内，最多能选 3 个字符串。
为什么不能正序？只给一个字符串 "10"，正确答案最多为 1。先从全零表开始。
正序先算 dp[1][1]，加入 "10" 后得到 1。这个值已经包含当前字符串。
继续正序会使用刚更新的 dp[1][1]，把同一个 "10" 计算两次。只有一个字符串，结果 2 不合法。
重新从全零表开始倒序更新。先算 dp[2][2]，此时 dp[1][1] 仍为 0，因此得到 1。
倒序最后才更新 dp[1][1]。之后不再回头更新 dp[2][2]，所以当前字符串只被选择一次。
容量可以为 0。缺少任意一种必需字符的容量，都不能选择该字符串。
倒序更新维护“当前字符串至多使用一次”的条件，二维状态则同时表示两种容量限制。
参考代码
class Solution: def findMaxForm(self, strs, m, n): dp = [[0]*(n+1) for _ in range(m+1)] for s in strs: z, o = s.count("0"), s.count("1") for i in range(m, z-1, -1): for j in range(n, o-1, -1): dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1) return dp[m][n]复杂度
- 时间：O(S + L(m+1)(n+1))，S 为所有字符串的总长度；L 为字符串个数；统计字符后逐串更新容量表
- 空间：O((m+1)(n+1))，二维容量表，包含容量为 0 的行和列
易错点
面试追问把动画讲成自己的话
追问为什么内层两维都要倒序？
追问和经典 01 背包有什么不同？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长回文子序列
LeetCode 516 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——围绕思路、代码与复杂度继续追问，获得分步反馈
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题