2209. Minimum White Tiles After Covering With Carpets
Description
You are given a 0-indexed binary string floor
, which represents the colors of tiles on a floor:
floor[i] = '0'
denotes that theith
tile of the floor is colored black.- On the other hand,
floor[i] = '1'
denotes that theith
tile of the floor is colored white.
You are also given numCarpets
and carpetLen
. You have numCarpets
black carpets, each of length carpetLen
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.
Example 1:
Input: floor = "10110101", 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.
Example 2:
Input: floor = "11111", 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.
Constraints:
1 <= carpetLen <= floor.length <= 1000
floor[i]
is either'0'
or'1'
.1 <= numCarpets <= 1000
Solutions
Solution 1: Memoization Search
Design a function $dfs(i, j)$ to represent the minimum number of white bricks that are not covered starting from index $i$ using $j$ carpets. The answer is $dfs(0, numCarpets)$.
For index $i$, we discuss different cases:
- If $i \ge n$, it means that all bricks have been covered, return $0$;
- If $floor[i] = 0$, there is no need to use a carpet, just skip it, that is, $dfs(i, j) = dfs(i + 1, j)$;
- If $j = 0$, we can directly calculate the number of remaining white bricks that have not been covered using the prefix sum array $s$, that is, $dfs(i, j) = s[n] - s[i]$;
- If $floor[i] = 1$, we can choose to use a carpet to cover it, or choose not to use a carpet to cover it, and take the minimum of the two, that is, $dfs(i, j) = min(dfs(i + 1, j), dfs(i + carpetLen, j - 1))$.
Use memoization search.
The time complexity is $O(n\times m)$, and the space complexity is $O(n\times m)$. Where $n$ and $m$ are the lengths of the string $floor$ and the value of $numCarpets$ respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|