第六章 - 高频考题(困难)
2209. 用地毯覆盖后的最少白色砖块

题目地址(2209. 用地毯覆盖后的最少白色砖块)

https://leetcode-cn.com/problems/minimum-white-tiles-after-covering-with-carpets/

题目描述

给你一个下标从 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
Python3 Code:
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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时 间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回 答。更多算法套路可以访问我的 LeetCode 题解仓库 :https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关 注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你 识别套路,高效刷题。