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

Question

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

我们考虑如何转移，和大多数转移方程一样，实际上就是一个选择问题。

• 如果选择盖住 floor[i] （不妨毯子尾部盖住 floor[i]），那么 dp[i][j] = dp[i - carpetLen][j - 1]
• 如果选择不盖住 floor[i]，那么 dp[i][j] = dp[i - 1][j] + int(floor[i] == '1')。 其中 int(floor[i] == '1') 表示如果 floor[i] 是黑的，那么漏出白色不受影响（+0） ，否则漏出白色多一块（+1）。

最后考虑 base case。

当 j == 0（没有毯子可用），我们如何考虑？此时：

dp[i][j] = dp[i-1][j] + int(floor[i] == '1')

那么当 i == 0 ，需要特殊考虑么？在这里是不需要的。

代码

语言支持：Python3

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        dp = [[0] * (numCarpets + 1) for _ in range(len(floor))]
        for i in range(len(floor)):
            for j in range(numCarpets + 1):
                if j == 0:
                    dp[i][j] = dp[i-1][j] + int(floor[i] == '1')
                    continue
                if i >= carpetLen and j > 0:
                    dp[i][j] = dp[i - carpetLen][j - 1]
                dp[i][j] = min(dp[i][j],  dp[i-1][j] + int(floor[i] == '1'))

        return dp[-1][-1]

复杂度分析

令 n 为 floor 长度。

• 时间复杂度：$O(n * numCarpets)$
• 空间复杂度：$O(n * numCarpets)$