题目描述
思路解析
一句话答案：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，列标 = 还能用几个 1。一个字符串都没放，dp 全是 0（一个都选不了）。
轮到 "10"，它要吃掉 1 个 0 和 1 个 1。下面从「预算最足」的右下角倒着往回更新——每格问：把它选进来划不划算？
算 dp[3][3]（剩 3 个 0、3 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[2][2]=0 基础上 +1 = 1。
选它更划算，dp[3][3] 升到 1。
算 dp[3][2]（剩 3 个 0、2 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[2][1]=0 基础上 +1 = 1。
选它更划算，dp[3][2] 升到 1。
算 dp[3][1]（剩 3 个 0、1 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[2][0]=0 基础上 +1 = 1。
选它更划算，dp[3][1] 升到 1。
算 dp[2][3]（剩 2 个 0、3 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[1][2]=0 基础上 +1 = 1。
选它更划算，dp[2][3] 升到 1。
算 dp[2][2]（剩 2 个 0、2 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[1][1]=0 基础上 +1 = 1。
选它更划算，dp[2][2] 升到 1。
算 dp[2][1]（剩 2 个 0、1 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[1][0]=0 基础上 +1 = 1。
选它更划算，dp[2][1] 升到 1。
算 dp[1][3]（剩 1 个 0、3 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[0][2]=0 基础上 +1 = 1。
选它更划算，dp[1][3] 升到 1。
算 dp[1][2]（剩 1 个 0、2 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[0][1]=0 基础上 +1 = 1。
选它更划算，dp[1][2] 升到 1。
算 dp[1][1]（剩 1 个 0、1 个 1）：不选 "10" 还是 0；选它就在「扣掉它消耗后」的 dp[0][0]=0 基础上 +1 = 1。
选它更划算，dp[1][1] 升到 1。
轮到 "0001"，它要吃掉 3 个 0 和 1 个 1。下面从「预算最足」的右下角倒着往回更新——每格问：把它选进来划不划算？
轮到 "1"，它要吃掉 0 个 0 和 1 个 1。下面从「预算最足」的右下角倒着往回更新——每格问：把它选进来划不划算？
算 dp[3][3]（剩 3 个 0、3 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[3][2]=1 基础上 +1 = 2。
选它更划算，dp[3][3] 升到 2。
算 dp[3][2]（剩 3 个 0、2 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[3][1]=1 基础上 +1 = 2。
选它更划算，dp[3][2] 升到 2。
算 dp[2][3]（剩 2 个 0、3 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[2][2]=1 基础上 +1 = 2。
选它更划算，dp[2][3] 升到 2。
算 dp[2][2]（剩 2 个 0、2 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[2][1]=1 基础上 +1 = 2。
选它更划算，dp[2][2] 升到 2。
算 dp[1][3]（剩 1 个 0、3 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[1][2]=1 基础上 +1 = 2。
选它更划算，dp[1][3] 升到 2。
算 dp[1][2]（剩 1 个 0、2 个 1）：不选 "1" 还是 1；选它就在「扣掉它消耗后」的 dp[1][1]=1 基础上 +1 = 2。
选它更划算，dp[1][2] 升到 2。
算 dp[0][3]（剩 0 个 0、3 个 1）：不选 "1" 还是 0；选它就在「扣掉它消耗后」的 dp[0][2]=0 基础上 +1 = 1。
选它更划算，dp[0][3] 升到 1。
算 dp[0][2]（剩 0 个 0、2 个 1）：不选 "1" 还是 0；选它就在「扣掉它消耗后」的 dp[0][1]=0 基础上 +1 = 1。
选它更划算，dp[0][2] 升到 1。
算 dp[0][1]（剩 0 个 0、1 个 1）：不选 "1" 还是 0；选它就在「扣掉它消耗后」的 dp[0][0]=0 基础上 +1 = 1。
选它更划算，dp[0][1] 升到 1。
轮到 "0"，它要吃掉 1 个 0 和 0 个 1。下面从「预算最足」的右下角倒着往回更新——每格问：把它选进来划不划算？
算 dp[3][3]（剩 3 个 0、3 个 1）：不选 "0" 还是 2；选它就在「扣掉它消耗后」的 dp[2][3]=2 基础上 +1 = 3。
选它更划算，dp[3][3] 升到 3。
算 dp[3][2]（剩 3 个 0、2 个 1）：不选 "0" 还是 2；选它就在「扣掉它消耗后」的 dp[2][2]=2 基础上 +1 = 3。
选它更划算，dp[3][2] 升到 3。
算 dp[3][1]（剩 3 个 0、1 个 1）：不选 "0" 还是 1；选它就在「扣掉它消耗后」的 dp[2][1]=1 基础上 +1 = 2。
选它更划算，dp[3][1] 升到 2。
算 dp[3][0]（剩 3 个 0、0 个 1）：不选 "0" 还是 0；选它就在「扣掉它消耗后」的 dp[2][0]=0 基础上 +1 = 1。
选它更划算，dp[3][0] 升到 1。
算 dp[2][3]（剩 2 个 0、3 个 1）：不选 "0" 还是 2；选它就在「扣掉它消耗后」的 dp[1][3]=2 基础上 +1 = 3。
选它更划算，dp[2][3] 升到 3。
算 dp[2][2]（剩 2 个 0、2 个 1）：不选 "0" 还是 2；选它就在「扣掉它消耗后」的 dp[1][2]=2 基础上 +1 = 3。
选它更划算，dp[2][2] 升到 3。
算 dp[2][1]（剩 2 个 0、1 个 1）：不选 "0" 还是 1；选它就在「扣掉它消耗后」的 dp[1][1]=1 基础上 +1 = 2。
选它更划算，dp[2][1] 升到 2。
算 dp[2][0]（剩 2 个 0、0 个 1）：不选 "0" 还是 0；选它就在「扣掉它消耗后」的 dp[1][0]=0 基础上 +1 = 1。
选它更划算，dp[2][0] 升到 1。
算 dp[1][1]（剩 1 个 0、1 个 1）：不选 "0" 还是 1；选它就在「扣掉它消耗后」的 dp[0][1]=1 基础上 +1 = 2。
选它更划算，dp[1][1] 升到 2。
算 dp[1][0]（剩 1 个 0、0 个 1）：不选 "0" 还是 0；选它就在「扣掉它消耗后」的 dp[0][0]=0 基础上 +1 = 1。
选它更划算，dp[1][0] 升到 1。
右下角 dp[3][3]=3：在「3 个 0、3 个 1」预算内，最多能选 3 个字符串。
边界先想清。
两个高频追问。
参考代码
def findMaxForm(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(L·m·n)，L 个串各扫一遍 m×n 表
- 空间：O(m·n)，只需二维 dp 表
易错点
面试追问把动画讲成自己的话
追问为什么内层两维都要倒序？
追问和经典 01 背包有什么不同？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长回文子序列
LeetCode 516 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题