当前位置：首页 > article >正文

力扣LeetCode: 2209 用地毯覆盖后的最少白色砖块

article 2025/2/22 12:57:41

题目：

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

floor[i] = '0' 表示地板上第 i 块砖块的颜色是黑色。
floor[i] = '1' 表示地板上第 i 块砖块的颜色是白色。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条黑色的地毯，每一条黑色的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的最少数目。

示例 1：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2：

输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。

提示：

1 <= carpetLen <= floor.length <= 1000
floor[i] 要么是 '0' ，要么是 '1' 。
1 <= numCarpets <= 1000

解法：动态规划

问题分析

我们有一个二进制字符串 floor，表示地板上砖块的颜色：

floor[i] = '0' 表示第 i 块砖是黑色。
floor[i] = '1' 表示第 i 块砖是白色。

我们有 numCarpets 条黑色地毯，每条地毯的长度为 carpetLen。我们的目标是用这些地毯覆盖尽可能多的白色砖块，使得未被覆盖的白色砖块数量最小。

动态规划思路

动态规划的核心思想是将问题分解为子问题，并通过状态转移方程逐步求解。我们需要定义一个状态，表示在某个位置使用一定数量的地毯时，未被覆盖的白色砖块的最小数量。

1. 定义状态

我们定义 dp[i][j] 表示：

覆盖前 i 块砖块（即 floor[0..i-1]）。
使用 j 条地毯。
未被覆盖的白色砖块的最小数量。

2. 状态转移方程

对于每一块砖块 i，我们有两种选择：

不使用地毯覆盖这块砖块：
- 如果这块砖是白色（floor[i-1] == '1'），则未被覆盖的白色砖块数量增加 1。
- 状态转移：dp[i][j] = dp[i-1][j] + (floor[i-1] == '1' ? 1 : 0)。
使用地毯覆盖这块砖块：
- 如果使用一条地毯覆盖从第 i-carpetLen 到第 i-1 块砖块，那么未被覆盖的白色砖块数量为 dp[i-carpetLen][j-1]。
- 状态转移：dp[i][j] = dp[i-carpetLen][j-1]。

我们需要在这两种选择中取最小值：

dp[i][j] = min(
    dp[i-1][j] + (floor[i-1] == '1' ? 1 : 0),  // 不使用地毯
    dp[i-carpetLen][j-1]                       // 使用地毯
);

3. 初始化

当没有砖块时（i = 0）：
- 无论有多少地毯，未被覆盖的白色砖块数量都是 0。
- dp[0][j] = 0，其中 0 <= j <= numCarpets。
当没有地毯时（j = 0）：
- 未被覆盖的白色砖块数量就是前 i 块砖中白色砖块的总数。
- dp[i][0] = dp[i-1][0] + (floor[i-1] == '1' ? 1 : 0)。

4. 最终结果

我们需要计算 dp[n][numCarpets]，其中 n 是砖块的总数。这表示覆盖所有砖块并使用所有地毯后，未被覆盖的白色砖块的最小数量。

代码实现

以下是完整的代码实现：

class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        // DP 表：dp[i][j] 表示前 i 块砖，使用 j 条地毯时，未被覆盖的白色砖块的最小数量
        vector<vector<int>> dp(n + 1, vector<int>(numCarpets + 1, 0));

        // 初始化：当没有地毯时，未被覆盖的白色砖块数量
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i-1][0] + (floor[i-1] == '1' ? 1 : 0);
        }

        // 填充 DP 表
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= numCarpets; ++j) {
                // 选择 1：不使用地毯覆盖第 i 块砖
                int option1 = dp[i-1][j] + (floor[i-1] == '1' ? 1 : 0);

                // 选择 2：使用地毯覆盖第 i 块砖
                int option2 = (i >= carpetLen) ? dp[i-carpetLen][j-1] : 0;

                // 取最小值
                dp[i][j] = min(option1, option2);
            }
        }

        // 返回结果
        return dp[n][numCarpets];
    }
};

示例解释

示例 1：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2

初始化：
- dp[i][0] 表示不使用地毯时，前 i 块砖中白色砖块的数量。
- 例如，dp[8][0] = 5（因为有 5 块白色砖块）。
填充 DP 表：
- 对于每块砖，尝试使用或不使用地毯，选择最优解。
- 最终 dp[8][2] = 2，表示使用 2 条地毯后，未被覆盖的白色砖块数量为 2。

示例 2：

输入：floor = "11111", numCarpets = 2, carpetLen = 3

初始化：
- dp[i][0] 表示不使用地毯时，前 i 块砖中白色砖块的数量。
- 例如，dp[5][0] = 5（因为有 5 块白色砖块）。
填充 DP 表：
- 使用 2 条长度为 3 的地毯，可以覆盖所有白色砖块。
- 最终 dp[5][2] = 0，表示所有白色砖块都被覆盖。