LeetCode 474. 一和零

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软
标签
数组 字符串 动态规划

题目描述

✅ 474. 一和零

image-20260928223104496

image-20260928223105317

题意分析

从给定的二进制字符串数组中选出尽量多的字符串，使所选内容中的零总数不超过 m，一总数不超过 n。返回选中的字符串个数，不是所选字符总数。

每个数组位置最多选一次，但相同内容的不同位置仍是独立候选。字符串必须整体选入或放弃，不能只拿其中部分字符；两种资源都可以有剩余，不要求恰好用完。

解法：二维 0-1 背包

核心思路

[!blue]

一个字符串只需记录它包含的零数 zeros 和一数 ones：选中它会同时消耗这两种容量，收益固定为一个字符串。因此这是每件物品最多选一次、同时有两种容量限制的背包问题。

定义 dp[i][j] 为：使用已经处理过的字符串，最多消耗 i 个零和 j 个一时，能够选出的最大数量。因为允许不选任何字符串，所有状态初始为零，不需要将部分容量标记为不可达。

处理一个字符串时，可以不选它，保留旧 dp[i][j]；也可以在容量足够时选它，得到 dp[i - zeros][j - ones] + 1。两者取最大值，覆盖了当前物品选或不选的所有情况。

状态表原地更新，必须保证来源仍然是上一物品轮次。外层零容量从大到小、内层一容量也从大到小：若 zeros > 0，来源位于尚未更新的更小行；若 zeros == 0，字符串非空，便有 ones > 0，来源位于本行尚未更新的更小列。因此当前字符串不会被重复使用，全零或全一的字符串也能正确处理。

解题步骤

  1. 创建大小为 (m + 1) × (n + 1) 的零状态表。
  2. 逐个读取字符串，统计它消耗的零数和一数。
  3. 零容量从 m 倒序到 zeros，一容量从 n 倒序到 ones，只处理容量足够的位置。
  4. 用不选的旧值与选入后的剩余容量最优数量加一取最大值。
  5. 处理全部字符串后，返回 dp[m][n]。

代码实现

class Solution {
    // dp[i][j] 表示在最多使用 i 个 0、j 个 1 时，最多能选择多少个字符串。
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0;
            int ones = 0;

            for (char c : s.toCharArray()) {
                if (c == '0') {
                    zeros++;
                } else {
                    ones++;
                }
            }

            // 两种容量都倒序，读取上一物品轮次的状态
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    // 比较不选与选入当前字符串，保留较多数量
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[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)
    }

    for _, s := range strs {
        zeros := 0
        ones := 0
        for i := 0; i < len(s); i++ {
            if s[i] == '0' {
                zeros++
            } else {
                ones++
            }
        }
        // 两种容量都倒序，读取上一物品轮次的状态
        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                // 比较不选与选入当前字符串，保留较多数量
                val := dp[i-zeros][j-ones] + 1
                if val > dp[i][j] {
                    dp[i][j] = val
                }
            }
        }
    }

    return dp[m][n]
}

复杂度分析

  • 时间复杂度：$O(T+L(m+1)(n+1))$，T 为全部字符数，L 为字符串数。统计字符共 $O(T)$，每件物品最多更新整张容量表。
  • 空间复杂度：状态表为 $O((m+1)(n+1))$。Java 当前实现逐串调用 toCharArray，还需最多 $O(S)$ 的临时字符数组，S 为最长字符串长度；Go 直接读取原串。

关键点总结

[!green]

  • 一个字符串是一件物品，两种字符数是它的资源消耗，收益为一。
  • 状态表示容量上限，不要求恰好填满，因此初始全零合法。
  • 两维倒序使转移来源尚未使用当前物品，维持每个位置最多选一次。
  • 最大化选中数量，转移取最大值，不能像方案计数一样直接相加。

易错点总结

[!yellow]

  • 容量正序更新，可能读到本轮已经加入当前字符串的状态，将同一物品反复使用。
  • 只倒序零容量、却正序更新一容量，当前字符串不含零时来源落在本行，仍可能重复选入。
  • 直接覆盖为“选入”结果，没有保留不选的旧值，可能丢掉更好的组合。
  • 容量不足仍访问减去消耗后的下标，会发生负下标越界。
  • 把相同内容的字符串去重，遗漏数组中不同位置本来都可被各选一次的机会。
  • 把收益加成字符串长度，求出的会是字符总量，而非题目要求的字符串个数。

相似题目

题目 难度 关联与区别
416. 分割等和子集 中等 同样每个元素最多选一次，本题每个字符串同时消耗0和1两个容量，需二维背包。
494. 目标和 中等 同样处理0/1选择，原题累计方案数，本题最大化被选字符串数量。
1049. 最后一块石头的重量 II 中等 用容量动态规划表示可达和或组合数；本题把容量扩展为零和一的两维预算，该题尽量把总重量划分得接近一半。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/82171475
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！