2209. 用地毯覆盖后的最少白色砖块¶

难度：困难

题目¶

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

Reference

题解¶

使用动态规划，定义dp[i][j]为从第i块砖开始，使用j条地毯，所能覆盖的最多白色砖块数，设地毯长度为\(L\)。则有状态转移方程：

\[ \text{dp}[i][j] = \max(\text{dp}[i + L][j - 1] + \sum_{k=i}^{i + L - 1} \text{floor}[k], \text{dp}[i + 1][j]) \]

以上算法需要重复计算一个地毯覆盖区间内白色砖块的数量。可以使用前缀和优化区间求和的过程，使用一个数组存储从第i块砖开始，到第i + L块砖结束，白色砖块的数量。

class Solution:
    def dfs(
        self, dp: List[List[Optional[int]]], range_whites: List[int],
        floor: str, currentPos: int, numCarpets: int, carpetLen: int, length: int
    ):
        while dp[currentPos][numCarpets] is None:
            if numCarpets == 0:
                dp[currentPos][numCarpets] = 0
                break
            if length - currentPos <= carpetLen:
                dp[currentPos][numCarpets] = sum(map(int, floor[currentPos:]))
                break
            place = self.dfs(
                dp, range_whites, floor,
                currentPos + carpetLen, numCarpets - 1, carpetLen, length
            ) + range_whites[currentPos]
            not_place = self.dfs(
                dp, range_whites, floor,
                currentPos + 1, numCarpets, carpetLen, length
            )
            dp[currentPos][numCarpets] = max(place, not_place)

        return dp[currentPos][numCarpets]

    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        length = len(floor)
        dp = [
            [None] * (numCarpets + 1)
            for i in range(length + 1)
        ]
        range_whites = [0] * (length + 1)
        for i in range(length - 1, -1, -1):
            range_whites[i] = range_whites[i + 1]
            if floor[i] == '1':
                range_whites[i] += 1
            if (i + carpetLen < length) and floor[i + carpetLen] == '1':
                range_whites[i] -= 1

        sum_whites = sum(map(int, floor))
        return sum_whites - self.dfs(
            dp, range_whites, floor, 0, numCarpets, carpetLen, length
        )

2209. 用地毯覆盖后的最少白色砖块¶

题目¶

题解¶

评论