[LeetCode] 每日一题 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 <= 1000floor[i]要么是'0'，要么是'1'。1 <= numCarpets <= 1000
解题思路
今天的题目要求使用给定数量的黑色地毯来尽量减少未被覆盖的白色砖块。我们需要处理的核心是如何在有限数量的地毯和每条地毯固定长度的情况下，最优地覆盖砖块
动态规划 是解决这类问题的有效方法。我们可以定义一个状态 dp[i][j] 表示使用 i 条地毯覆盖前 j 块砖块时，剩余的白色砖块最少的数量。状态转移的关键是：每次覆盖的选择可以是从 j - carpetLen 到 j 这段砖块，或者不覆盖当前位置砖块，即保留原状态的值
具体来说，初始状态是 dp[0][j]，表示没有地毯时覆盖前 j 块砖块的白色砖块数，即累计所有未覆盖的白色砖块数。接下来，对于每条地毯的覆盖，我们要比较以下两种情况：
不覆盖当前砖块，则结果是
dp[i][j-1] + 当前砖块是否为白色覆盖当前砖块，则结果是
dp[i-1][max(j - carpetLen, 0)]，即从前面适当的位置开始覆盖
最终，结果为 dp[numCarpets][floor.length()]，即使用所有地毯后，覆盖整个地板的最小未覆盖白色砖块数
代码实现
class Solution {
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
// dp[i][j]表示使用 i 个地毯，铺前 j 个地板块，最少剩余的白色砖块数
int[][] dp = new int[numCarpets + 1][floor.length() + 1];
// 初始化第一行dp[0][j]，表示没有地毯时的白色砖块数
for (int j = 1; j <= floor.length(); j++) {
dp[0][j] = dp[0][j - 1] + floor.charAt(j - 1) - '0';
}
for (int i = 1; i <= numCarpets; i++) {
for (int j = 1; j <= floor.length(); j++) {
dp[i][j] = Math.min(dp[i][j - 1] + floor.charAt(j - 1) - '0', dp[i - 1][Math.max(j - carpetLen, 0)]);
}
}
return dp[numCarpets][floor.length()];
}
}复杂度分析
时间复杂度：
O(numCarpets * floor.length())。我们需要通过动态规划计算numCarpets条地毯和floor.length()块砖块的状态转移。每个状态计算都涉及一个常数的操作空间复杂度：
O(numCarpets * floor.length())。我们需要一个二维数组dp来存储每个状态的值，大小为(numCarpets + 1) * (floor.length() + 1)
总结
这道题通过动态规划解决了在有限地毯数量和固定地毯长度下，最小化剩余白色砖块的挑战。通过将问题转化为计算覆盖区间的最优策略，我们能够逐步计算并更新每个可能状态的最小未覆盖白色砖块数。最终，我们得到的是使用所有地毯后的最小剩余白色砖块数
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。