题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

解题思路

识别问题

题目要求： 给你一个字符串数组 strs 和两个整数 m (0的容量) 和 n (1的容量)。你要从 strs 中选出一个子集，使得这个子集中所有字符串的 '0' 的总数不超过 m，'1' 的总数不超过 n。你的目标是让这个子集的长度（即字符串的个数）最大。
分析：
1. 我们有一堆“物品”（strs 里的每个字符串）。
2. 对于每个物品，我们只有两种选择：“选” 或 “不选”。
3. 我们的目标是最大化我们“选”的物品数量。
4. 我们有两个限制条件（“背包容量”）：'0' 的总数不能超过 m，'1' 的总数不能超过 n。
结论： 这是一个0/1背包问题。

更具体地说，它是一个：

二维费用（或二维容量）的 0/1 背包问题（费用1是 '0' 的个数，费用2是 '1' 的个数）。
每个物品的价值都是 1（因为我们关心的是物品的数量，而不是其他价值）。

DP规划

既然是背包问题，我们首选动态规划。

1. 状态定义

我们需要一个 dp 表来记录我们的“最优解”。因为我们有两个限制（m 和 n），所以我们的 dp 表至少需要是二维的。

dp[i][j]：表示使用 i 个 '0' 和 j 个 '1' 所能组成的最大子集长度。

我们的目标就是求 dp[m][n]。

2. 状态转移

我们如何填满这个 dp 表？

我们必须遍历每一件物品（即 strs 数组中的每一个字符串 s）。对于每一个 s，我们都用它来更新整个 dp 表。

当我们拿到一个新字符串 s 时（假设它有 zeros 个 '0' 和 ones 个 '1'），我们遍历 dp 表中的所有格子 dp[i][j]。对于 dp[i][j]，我们有两种决策：

不选这个字符串 s：
- 那么 dp[i][j] 的值保持不变（继承自_考虑 s 之前_的最优解）。
- dp[i][j] = dp[i][j]
选这个字符串 s：
- 前提：我们必须“买得起”它，即 i >= zeros 且 j >= ones。
- 如果我们选了 s，我们的子集长度就 +1。
- 这个 +1 是加在**“为 s 腾出空间”**后的最优解之上的。
- “腾出空间”的最优解是 dp[i - zeros][j - ones]。
- 所以，选择 s 的方案能达到的最大长度是 1 + dp[i - zeros][j - ones]。

最终决策： 我们在“不选”和“选”之间取一个最大值。 dp[i][j] = max( dp[i][j], 1 + dp[i - zeros][j - ones] )

注意，为了保证每个物品 s 只被“选”一次（这是 0/1 背包的核心），我们在更新 dp[i][j] 时，i 和 j 必须倒序遍历。

for s in strs: (遍历物品)
- (计算 s 的 zeros 和 ones)
- for i from m down to zeros: (倒序遍历 '0' 的容量)
  - for j from n down to ones: (倒序遍历 '1' 的容量)
    - dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

（如果你正序遍历，dp[i - zeros][j - ones] 就会是_本轮_被 s 更新过的值，导致 s 被重复计算，变成了“完全背包问题”）。

时间复杂度: O(L * m * n) (L = strs 长度)
空间复杂度: O(m * n)

性能瓶颈

标准解法在大多数情况下都很好。但我们思考一个极端情况：

strs = ["10", "10", "10", ..., "10"] (共 100 万个 "10")
m = 5, n = 3

标准解法会怎么做？它会遍历 L = 100万 次。在每次循环中，它都拿着 "10" (1个0, 1个1) 去更新 dp 表，做着完全重复的无用功。

瓶颈：标准 0/1 背包解法无法处理“物品重复”的情况，因此我们需要一个优化重复物品的解法。

这个思路的核心是：不遍历 100 万次，而是先把物品“打包”

1. 分组 (0/1 背包 -> 多重背包)

先用一个哈希表 (map) 遍历 strs。
统计：
- 物品 "10" (成本 1, 1)：有 100 万个。
- 物品 "001" (成本 2, 1)：有 50 个。
- ...
问题转化：我们的问题从 0/1 背包（L 个物品，每个只能选1次）变成了多重背包（U 种物品，每种物品有 k 个）。

2. 拆分 (多重背包 -> 0/1 背包)

我们如何高效地处理“100万个 "10"”呢？
我们不能循环 100 万次（O(k)）来尝试“拿1个”、“拿2个”...
二进制拆分：
- 任何一个数 k (比如 100万) 都可以被拆成 1 + 2 + 4 + 8 + ... 的和。
- 我们把“100万个 "10"”这一组物品，拆分成 log(k)（约 20）个**“物品包”**：
  1. "1个'10'" (包1: 成本 1*cost, 价值 1)
  2. "2个'10'" (包2: 成本 2*cost, 价值 2)
  3. "4个'10'" (包3: 成本 4*cost, 价值 4)
  4. ...
  5. "剩余的'10'" (包20: 成本 ... , 价值 ...)
为什么？ 因为通过对这 20 个“物品包”进行0/1选择（选或不选），我们就能组合出 0 ~ 100万之间的任意数量。
- 想拿 7 个？-> 选 (包1 + 包2 + 包3)。
- 想拿 9 个？-> 选 (包1 + 包8)。

3. 最终求解

遍历 strs，用哈希表进行分组（步骤 4.1）。
遍历哈希表，对每一种物品（k 个），都进行二进制拆分，生成一个 log(k) 大小的“物品包”列表（步骤 4.2）。
运行标准 DP（步骤 2）来处理这个新的“物品包”列表。

时间复杂度: O( (U * logK) * m * n )
- U = 不重复字符串的种类数
- K = 物品的最大重复次数
空间复杂度: O(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)
    }

    // 遍历 L 个物品
    for _, str := range strs {
        zeros := 0
        ones := 0
        for _, r := range str {
            if r == '0' {
                zeros++
            } else {
                ones++
            }
        }

        // 倒序更新 dp 表
        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                // 决策：(不选) vs (选)
                dp[i][j] = max(dp[i][j], 1 + dp[i-zeros][j-ones])
            }
        }
    }

    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

优化解

type Packet struct {
	cost0 int // 这个包总共需要 cost0 个 '0'
	cost1 int // 这个包总共需要 cost1 个 '1'
	value int // 这个包包含 value 个原始字符串 (即价值)
}

func findMaxForm(strs []string, m int, n int) int {

	// --- 步骤 1：哈希分组 ---
	// 统计每种字符串的 "成本" (0的个数, 1的个数) 和 "数量" (count)
	
	// itemCosts 存储 {"10": [1, 1]} (1个0, 1个1)
	itemCosts := make(map[string][2]int) 
	// itemCounts 存储 {"10": 5} (有5个 "10")
	itemCounts := make(map[string]int)

	for _, str := range strs {
		// 如果是第一次见这个字符串，计算它的成本
		if _, seen := itemCosts[str]; !seen {
			zeros, ones := 0, 0
			for _, r := range str {
				if r == '0' {
					zeros++
				} else {
					ones++
				}
			}
			itemCosts[str] = [2]int{zeros, ones}
		}
		// 无论如何，数量+1
		itemCounts[str]++
	}

	// --- 步骤 2：二进制拆分 (多重背包 -> 0/1背包) ---
	// 我们不再有 L 个物品，而是有一堆 "物品包"
	// 例如: 13 个 "10" (成本 1,1) 会被拆分成：
	// 包1: 1个 "10" (成本 1,1; 价值 1)
	// 包2: 2个 "10" (成本 2,2; 价值 2)
	// 包3: 4个 "10" (成本 4,4; 价值 4)
	// 包4: 6个 "10" (成本 6,6; 价值 6) (余数)
	// 这 4 个包可以组合出 0~13 任意数量的 "10"，且每个包都是 0/1 选择
	
	packets := []Packet{}
	for str, count := range itemCounts {
		costs := itemCosts[str]
		c0 := costs[0]
		c1 := costs[1]

		// k 是包的大小 (1, 2, 4, 8, ...)
		for k := 1; count >= k; k *= 2 {
			packets = append(packets, Packet{
				cost0: c0 * k, // k 个物品的总 0 成本
				cost1: c1 * k, // k 个物品的总 1 成本
				value: k,      // k 个物品的总价值 (长度)
			})
			count -= k
		}
		// 如果还有余数 (比如 count=13, 拆了 1,2,4,8, 余数为 6)
		if count > 0 {
			packets = append(packets, Packet{
				cost0: c0 * count,
				cost1: c1 * count,
				value: count,
			})
		}
	}

	// --- 步骤 3：标准的 0/1 背包 (空间优化) ---
	// dp[i][j] = 用 i 个 0 和 j 个 1 能获得的最大价值 (长度)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 遍历所有的“物品包” (而不是 L 个原始物品)
	for _, packet := range packets {
		// 必须倒序遍历，保证每个“物品包”只被用一次
		for i := m; i >= packet.cost0; i-- {
			for j := n; j >= packet.cost1; j-- {
				// 决策：不选这个包 vs 选这个包
				dp[i][j] = max(
					dp[i][j], // 不选
					dp[i-packet.cost0][j-packet.cost1] + packet.value, // 选
				)
			}
		}
	}

	// 最终答案
	return dp[m][n]
}

474. 一和零

beautifulremi

题目