LeetCode 题解工作台
用地毯覆盖后的最少白色砖块
给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。 floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。 floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。 同时给你 numCarpets 和 carpetLen 。你有 nu…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, j)$ 表示从下标 开始，使用 条地毯，最少有多少个白色砖块没有被覆盖。答案即为 $\textit{dfs}(0, \textit{numCarpets})$。 对于下标 ，我们分情况讨论：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 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 <= 1000floor[i]要么是'0'，要么是'1'。1 <= numCarpets <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 表示从下标 开始，使用 条地毯，最少有多少个白色砖块没有被覆盖。答案即为 。
对于下标 ，我们分情况讨论：
- 如果 ，说明已经覆盖完所有砖块，返回 ；
- 如果 ，则不需要使用地毯，直接跳过即可，即 ；
- 如果 ，那么我们可以直接利用前缀和数组 计算出剩余未被覆盖的白色砖块的数目，即 ；
- 如果 ，那么我们可以选择使用地毯覆盖，也可以选择不使用地毯覆盖，取两者的最小值即可，即 。
记忆化搜索即可。
时间复杂度 ，空间复杂度 。其中 和 分别为字符串 的长度和 的值。
class Solution:
def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= n:
return 0
if floor[i] == "0":
return dfs(i + 1, j)
if j == 0:
return s[-1] - s[i]
return min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1))
n = len(floor)
s = [0] * (n + 1)
for i, c in enumerate(floor):
s[i + 1] = s[i] + int(c == "1")
ans = dfs(0, numCarpets)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n _numCarpets) where n is the length of floor, since each DP state depends on remaining carpets. Space can be O(n_ numCarpets) for full DP table, or optimized to O(n) per carpet iteration using rolling arrays. Prefix sum computation adds O(n) time and space but improves efficiency for range calculations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for correct DP state definition and transitions.
- question_mark
Check handling of overlapping carpets and full coverage scenarios.
- question_mark
Ask if prefix sums can optimize repeated white tile counting.
常见陷阱
外企场景- error
Forgetting carpets can overlap, leading to incorrect minimum counts.
- error
Not handling edge cases where carpetLen exceeds remaining floor length.
- error
Incorrectly updating DP states when skipping tiles versus placing a carpet.
进阶变体
外企场景- arrow_right_alt
Change to minimize black tiles visible instead of white tiles.
- arrow_right_alt
Allow carpets of varying lengths instead of a fixed carpetLen.
- arrow_right_alt
Provide multiple floors and require independent minimization for each.