Hard

题目描述

给你一个下标从 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

解题思路

解题思路

这是一个经典的动态规划问题。我们需要决定在每个位置是否放置地毯来最小化剩余的白色瓷砖数量。

核心思路：

我们定义 dp[i][j] 表示从位置 i 到字符串末尾，使用至多 j 条地毯能够覆盖的最多白色瓷砖数量。最终答案就是总白色瓷砖数减去 dp[0][numCarpets]。

状态转移：

对于每个位置 i，我们有两种选择：

  1. 不在位置 i 放置地毯：dp[i][j] = dp[i+1][j]
  2. 在位置 i 放置地毯：地毯覆盖从 i 到 i+carpetLen-1 的区域，转移为 dp[i+carpetLen][j-1] + covered_white

其中 covered_white 是这段区域内的白色瓷砖数量，可以通过前缀和快速计算。

优化技巧：

  • 使用前缀和数组快速计算任意区间的白色瓷砖数量
  • 从后往前进行动态规划，避免重复计算
  • 边界条件：当 j = 0 或 i >= n 时，无法再覆盖更多瓷砖

时间复杂度为 O(n × numCarpets)，空间复杂度为 O(n × numCarpets)。

代码实现

class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        
        // 计算前缀和，用于快速计算区间内的白色瓷砖数量
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (floor[i] == '1' ? 1 : 0);
        }
        
        // dp[i][j] 表示从位置i开始，用j条地毯最多能覆盖的白色瓷砖数
        vector<vector<int>> dp(n + 1, vector<int>(numCarpets + 1, 0));
        
        // 从后往前填表
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= numCarpets; j++) {
                // 选择1：不在位置i放地毯
                dp[i][j] = dp[i + 1][j];
                
                // 选择2：在位置i放地毯（如果还有地毯可用）
                if (j > 0) {
                    int end = min(i + carpetLen, n);
                    int covered = prefixSum[end] - prefixSum[i];
                    dp[i][j] = max(dp[i][j], dp[end][j - 1] + covered);
                }
            }
        }
        
        return prefixSum[n] - dp[0][numCarpets];
    }
};

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        
        # 计算前缀和
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + (1 if floor[i] == '1' else 0)
        
        # dp[i][j] 表示从位置i开始，用j条地毯最多能覆盖的白色瓷砖数
        dp = [[0] * (numCarpets + 1) for _ in range(n + 1)]
        
        # 从后往前填表
        for i in range(n - 1, -1, -1):
            for j in range(numCarpets + 1):
                # 选择1：不在位置i放地毯
                dp[i][j] = dp[i + 1][j]
                
                # 选择2：在位置i放地毯
                if j > 0:
                    end = min(i + carpetLen, n)
                    covered = prefix_sum[end] - prefix_sum[i]
                    dp[i][j] = max(dp[i][j], dp[end][j - 1] + covered)
        
        return prefix_sum[n] - dp[0][numCarpets]

public class Solution {
    public int MinimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.Length;
        
        // 计算前缀和
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (floor[i] == '1' ? 1 : 0);
        }
        
        // dp[i][j] 表示从位置i开始，用j条地毯最多能覆盖的白色瓷砖数
        int[,] dp = new int[n + 1, numCarpets + 1];
        
        // 从后往前填表
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= numCarpets; j++) {
                // 选择1：不在位置i放地毯
                dp[i, j] = dp[i + 1, j];
                
                // 选择2：在位置i放地毯
                if (j > 0) {
                    int end = Math.Min(i + carpetLen, n);
                    int covered = prefixSum[end] - prefixSum[i];
                    dp[i, j] = Math.Max(dp[i, j], dp[end, j - 1] + covered);
                }
            }
        }
        
        return prefixSum[n] - dp[0, numCarpets];
    }
}

var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
    const n = floor.length;
    
    // 计算前缀和
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + (floor[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n × numCarpets)，其中 n 为字符串长度，需要填充 n × numCarpets 的动态规划表
空间复杂度O(n × numCarpets)，用于存储动态规划表和前缀和数组

相关题目