一和零为什么是二维 0-1 背包？如何用动态规划处理两个容量限制？

简化版

一和零是二维 0-1 背包：每个字符串只能选一次，消耗若干个 0 和若干个 1，价值是 1。定义 dp[i][j] 表示最多使用 i 个 0、j 个 1 能选的最大字符串数，遍历每个字符串时两个容量都要倒序更新。

详细版

先统计每个字符串的 zero 和 one 数量。对于每个字符串，执行 for i from m down to zero、for j from n down to one，转移为 dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1)。倒序是为了保证每个字符串只被选一次。

时间复杂度是 O(len * m * n)，空间复杂度 O(mn)。这题的核心不是字符串处理，而是识别“两个容量限制 + 每个物品选或不选”的 0-1 背包模型。

完整版教学

一、为什么这是背包问题

题目给你一组字符串、最多 m 个 0、最多 n 个 1，问最多能选多少个字符串。每个字符串有两个成本：消耗 0 的数量和消耗 1 的数量；每选一个字符串，收益是 1。

物品：字符串
成本：zeroCount、oneCount
容量：m 个 0、n 个 1
价值：1

每个字符串只能选一次，所以它不是完全背包，而是 0-1 背包。

二、状态定义为什么是二维容量

普通 0-1 背包只有一个容量，比如重量。这题有两个限制，必须同时满足，所以状态要有两个容量维度。

dp[i][j] = 最多使用 i 个 0、j 个 1 时，能选出的最大字符串数量

维度	含义
`i`	0 的容量
`j`	1 的容量
`dp[i][j]`	能选的最大字符串数

如果只记录一个容量，会丢失另一个约束，导致选出不合法组合。

三、转移公式怎么来

对当前字符串，统计得到：

zero = 当前字符串中 0 的个数
one = 当前字符串中 1 的个数

当前状态有两种选择：

不选：dp[i][j]
选：dp[i-zero][j-one] + 1

所以：

dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1)

这个公式和普通 0-1 背包一样，只是容量从一维变成二维。

四、为什么两个循环都要倒序

倒序的目的是防止当前字符串在同一轮被重复使用。比如字符串 "0"，如果 i 正序更新，dp[1] 更新后可能马上影响 dp[2]，相当于同一个 "0" 被选了两次。

0-1 背包：容量倒序，物品只能用一次
完全背包：容量正序，物品可以重复用

记忆钩子：只要题目说“每个元素最多选一次”，背包容量更新先条件反射想倒序。

二维容量也一样，i 和 j 都要从大到小遍历。

五、用例子看状态更新

假设 strs=["10","0","1"]，m=1,n=1。

"10" 消耗 1 个 0、1 个 1，价值 1
"0"  消耗 1 个 0、0 个 1，价值 1
"1"  消耗 0 个 0、1 个 1，价值 1

最优选择是 "0" 和 "1"，答案 2。虽然 "10" 单个字符串也刚好占满容量，但价值只有 1。

这说明 DP 比较的是组合数量，不是单个字符串是否更“饱满”。

六、代码模板

int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m + 1][n + 1];
    for (String s : strs) {
        int zero = 0, one = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') zero++;
            else one++;
        }
        for (int i = m; i >= zero; i--) {
            for (int j = n; j >= one; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
            }
        }
    }
    return dp[m][n];
}

初始化为 0 是合理的，因为不选任何字符串时数量就是 0。

七、常见误区与追问

误区：把它当成普通一维背包。 两个容量限制都必须保留，否则会选出超过 0 或 1 数量的组合。
误区：容量正序遍历。 正序会让同一个字符串被重复选择。
误区：把字符串长度当成唯一成本。 长度相同的字符串，0 和 1 的分布可能完全不同。
追问：价值为什么是 1？ 目标是最大字符串数量，每选一个字符串贡献 1。
追问：如果每个字符串有不同价值怎么办？ 把 +1 改成 +value，模型仍是二维 0-1 背包。
追问：复杂度瓶颈在哪里？ 每个字符串都要更新一个 m*n 的容量表。

八、加强记忆

一和零的识别口令是“两种资源、每个字符串选一次、收益是数量”。两种资源让状态变成 dp[zero][one]，选一次让容量必须倒序，收益是数量让转移里加 1。别被字符串外壳迷惑，它本质就是二维 0-1 背包。

简化版

详细版