minimum-white-tiles-after-covering-with-carpets

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed binary string <code>floor</code>, which represents the colors of tiles on a floor:

<ul>
	<li><code>floor[i] = &#39;0&#39;</code> denotes that the <code>ith</code> tile of the floor is colored black.</li>
	<li>On the other hand, <code>floor[i] = &#39;1&#39;</code> denotes that the <code>ith</code> tile of the floor is colored white.</li>
</ul>

You are also given <code>numCarpets</code> and <code>carpetLen</code>. You have <code>numCarpets</code> black carpets, each of length <code>carpetLen</code> tiles. Cover the tiles with the given carpets such that the number of white tiles still visible is minimum. Carpets may overlap one another.

Return the minimum number of white tiles still visible.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/10/ex1-1.png" style="width: 400px; height: 73px;" />
<pre>
Input: floor = &quot;10110101&quot;, numCarpets = 2, carpetLen = 2
Output: 2
Explanation: 
The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible.
No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/10/ex2.png" style="width: 353px; height: 123px;" />
<pre>
Input: floor = &quot;11111&quot;, numCarpets = 2, carpetLen = 3
Output: 0
Explanation: 
The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible.
Note that the carpets are able to overlap one another.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= carpetLen &lt;= floor.length &lt;= 1000</code></li>
	<li><code>floor[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= numCarpets &lt;= 1000</code></li>
</ul>

minimumWhiteTiles

Minimum White Tiles After Covering With Carpets

Edit Distance

edit-distance

编辑距离

String

Dynamic Programming

Prefix Sum

给你一个下标从&nbsp;0&nbsp;开始的 二进制&nbsp;字符串&nbsp;<code>floor</code>&nbsp;，它表示地板上砖块的颜色。

<ul>
	<li><code>floor[i] = '0'</code>&nbsp;表示地板上第&nbsp;<code>i</code>&nbsp;块砖块的颜色是 黑色&nbsp;。</li>
	<li><code>floor[i] = '1'</code>&nbsp;表示地板上第&nbsp;<code>i</code>&nbsp;块砖块的颜色是 白色&nbsp;。</li>
</ul>

同时给你&nbsp;<code>numCarpets</code> 和&nbsp;<code>carpetLen</code>&nbsp;。你有&nbsp;<code>numCarpets</code>&nbsp;条&nbsp;黑色&nbsp;的地毯，每一条&nbsp;黑色&nbsp;的地毯长度都为&nbsp;<code>carpetLen</code>&nbsp;块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色&nbsp;砖块的数目 最小&nbsp;。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少&nbsp;数目。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/10/ex1-1.png" style="width: 400px; height: 73px;">

<pre>输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/10/ex2.png" style="width: 353px; height: 123px;">

<pre>输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= carpetLen &lt;= floor.length &lt;= 1000</code></li>
	<li><code>floor[i]</code> 要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code>&nbsp;。</li>
	<li><code>1 &lt;= numCarpets &lt;= 1000</code></li>
</ul>