一和零 图解题解

两个预算下最多能挑几个二进制串

给一堆二进制字符串 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 就该停，预算不够付它就选不了，再减会取到负下标。

Python

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]

C++

int findMaxForm(vector<string>& strs, int m, int n){
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(auto& s : strs){
        int z = count(s.begin(), s.end(), '0'), o = s.size() - z;
        for(int i = m; i >= z; i--)
            for(int j = n; j >= o; j--)
                dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1);
    }
    return dp[m][n];
}

Java

int findMaxForm(String[] strs, int m, int n){
    int[][] dp = new int[m+1][n+1];
    for(String s : strs){
        int z = 0;
        for(int t = 0; t < s.length(); t++) if(s.charAt(t)=='0') z++;
        int o = s.length() - z;
        for(int i = m; i >= z; i--)
            for(int j = n; j >= o; j--)
                dp[i][j] = Math.max(dp[i][j], dp[i-z][j-o] + 1);
    }
    return dp[m][n];
}