【LeetCode】动态规划—474. 一和零（附完整Python/C++代码）

动态规划—474. 一和零

• 题目描述
• 前言
• 基本思路
  • 1. 问题定义
  • • 举例：
  • 2. 理解问题和递推关系
  • • 动态规划思想：
    • 状态定义：
    • 状态转移方程：
    • 边界条件：
  • 3. 解决方法
  • • 动态规划方法
    • 伪代码：
  • 4. 进一步优化
  • 5. 小总结
• Python代码
• • • Python代码解释
• C++代码
• • • C++代码解释
• 总结

题目描述

在这里插入图片描述

前言

一和零 是一个典型的 0-1 背包问题。给定若干个仅由 0 和 1 组成的二进制字符串，再给定两个整数 m 和 n，表示最多可以包含的 0 和 1 的数量。要求通过选取若干个字符串，使得这些字符串的总 0 和 1 的数量不超过 m 和 n，并且在这些条件下选取的字符串数量最多。

基本思路

1. 问题定义

给定一个字符串数组 strs，每个字符串仅由 0 和 1 组成。同时给定两个整数 m 和 n，要求在 m 个 0 和 n 个 1 的限制下，选出最多的字符串。

举例：

• 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
• 输出：4
• 解释：我们可以选取 "10", "0001", "1", "0" 四个字符串，总共包含 5 个 0 和 3 个 1。

2. 理解问题和递推关系

动态规划思想：

这是一个典型的 0-1 背包问题。我们可以把每个字符串看作一个物品，字符串中 0 的数量相当于物品的重量1，1 的数量相当于物品的重量2。我们希望在 m 和 n 的限制下，尽可能选取更多的字符串。

状态定义：

• dp[i][j] 表示使用不超过 i 个 0 和 j 个 1 时，可以选取的最大字符串数量。

状态转移方程：

• 对于每个字符串 str，我们先统计出它包含的 0 和 1 的数量 zero_num 和 one_num。
• 然后我们使用类似 0-1 背包 的倒序遍历来更新 dp 数组：

边界条件：

• 初始化 dp 数组时，dp[0][0] = 0，表示在不使用任何 0 和 1 的情况下，没有选择任何字符串。

3. 解决方法

动态规划方法

1. 初始化：创建一个二维数组 dp，其中 dp[i][j] 表示使用 i 个 0 和 j 个 1 时的最大字符串数量。
2. 状态转移：遍历字符串 strs，计算每个字符串中的 0 和 1 数量，然后从后向前更新 dp 数组，确保每个字符串最多使用一次。
3. 返回结果：最终的结果为 dp[m][n]，即使用最多 m 个 0 和 n 个 1 时可以选择的最多字符串数量。

伪代码：

initialize dp array with dp[0][0] = 0
for each str in strs:
    count the number of zeros and ones in str
    for i from m to zero_num:
        for j from n to one_num:
            dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)
return dp[m][n]

4. 进一步优化

• 时间复杂度：时间复杂度为 O(len(strs) * m * n)，其中 len(strs) 是字符串数组的长度，m 和 n 分别是可用的 0 和 1 的数量。
• 空间复杂度：空间复杂度为 O(m * n)，因为我们只需要存储一个大小为 m+1 和 n+1 的二维数组 dp。

5. 小总结

• 递推思路：这是一个典型的 0-1 背包问题，使用二维动态规划数组来表示状态，并根据每个字符串的 0 和 1 数量来更新状态。
• 时间复杂度：时间复杂度为 O(len(strs) * m * n)，适合处理中等规模的输入。

以上就是一和零问题的基本思路。

Python代码

class Solution:
    def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
        # 初始化dp数组，dp[i][j]表示用i个0和j个1最多可以选取的字符串数量
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 遍历每个字符串，计算其0和1的数量
        for s in strs:
            zero_num = s.count('0')
            one_num = s.count('1')
            
            # 倒序遍历以确保每个字符串只能使用一次
            for i in range(m, zero_num - 1, -1):
                for j in range(n, one_num - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)

        return dp[m][n]  # 返回最多能选取的字符串数量

Python代码解释

1. 初始化：定义一个二维数组 dp，其中 dp[i][j] 表示用不超过 i 个 0 和 j 个 1 时，可以选取的最大字符串数量。
2. 动态规划递推：遍历每个字符串，计算它的 0 和 1 数量，更新 dp 数组。
3. 返回结果：最终返回 dp[m][n]，即最多可以选取的字符串数量。

C++代码

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 初始化dp数组，dp[i][j]表示用i个0和j个1最多可以选取的字符串数量
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // 遍历每个字符串，计算其0和1的数量
        for (const string& s : strs) {
            int zero_num = count(s.begin(), s.end(), '0');
            int one_num = count(s.begin(), s.end(), '1');
            
            // 倒序遍历以确保每个字符串只能使用一次
            for (int i = m; i >= zero_num; --i) {
                for (int j = n; j >= one_num; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1);
                }
            }
        }

        return dp[m][n];  // 返回最多能选取的字符串数量
    }
};

C++代码解释

1. 初始化：定义一个二维数组 dp，dp[i][j] 表示用不超过 i 个 0 和 j 个 1 时，可以选取的最大字符串数量。
2. 动态规划递推：遍历每个字符串，计算其 0 和 1 数量，然后更新 dp 数组。
3. 返回结果：最终返回 dp[m][n]，即最多可以选取的字符串数量。

总结

• 核心思想：这是一个典型的 0-1 背包问题，我们通过使用二维动态规划数组来表示状态，利用每个字符串的 0 和 1 数量来更新状态。
• 时间复杂度：时间复杂度为 O(len(strs) * m * n)，适合处理中等规模的输入。
• 空间复杂度：空间复杂度为 O(m * n)，只需要存储二维 dp 数组。