# 2209. 用地毯覆盖后的最少白色砖块
### 题目地址(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
```
### 前置知识
* 动态规划
### 公司
* 暂无
### 思路
定义 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（没有毯子可用），我们如何考虑？此时：
```py
dp[i][j] = dp[i-1][j] + int(floor[i] == '1')
```
那么当 i == 0 ，需要特殊考虑么？在这里是不需要的。
### 关键点
*
### 代码
* 语言支持：Python3
Python3 Code:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时 间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回 答。更多算法套路可以访问我的 LeetCode 题解仓库 ： 。 目前已经 40K star 啦。大家也可以关 注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你 识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2209.minimum-white-tiles-after-covering-with-carpets.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.