用地毯覆盖后的最少白色砖块

难度: Hard

给你一个下标从 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

Submission

运行时间: 832 ms

内存: 27.0 MB

class Solution:
    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 剪枝
        f = [[0] * m for _ in range(n + 1)]
        f[0][0] = (floor[0] == '1')
        for i in range(1, m):
            f[0][i] = f[0][i - 1] + (floor[i] == '1')
        for i in range(1, n + 1):
            # j < carpetLen * i 的 f[i][j] 均为 0
            for j in range(carpetLen * i, m):
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])
        return f[n][-1]

Explain

这个题解使用了动态规划的方法来解决问题。定义了一个二维数组 f[i][j]，其中 i 表示使用了 i 条地毯，j 表示考虑到第 j 块砖块时的最小未覆盖白色砖块数。首先初始化 f[0][j] 表示不使用地毯时的未覆盖白色砖块数，即直接统计前 j 个砖块中白色砖块的数量。对于每个 i (1 <= i <= n)，计算使用 i 条地毯覆盖时的情况。具体地，如果放置一条地毯覆盖从 j-carpetLen 到 j 的区间，那么 f[i][j] 可以从 f[i-1][j-carpetLen] 转移过来。也可以选择不放地毯在位置 j，即 f[i][j] 直接从 f[i][j-1] 转移，这时要加上 j 位置的砖块是否为白色。最终，f[n][-1] 就是使用 n 条地毯覆盖所有砖块时的最小未覆盖白色砖块数。

时间复杂度: O(n*m)

空间复杂度: O(n*m)

class Solution:
    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 如果地毯总长度大于等于地板长度，直接返回 0
        f = [[0] * m for _ in range(n + 1)]
        f[0][0] = (floor[0] == '1')  # 初始化第一行，无地毯覆盖情况下的白砖数量
        for i in range(1, m):
            f[0][i] = f[0][i - 1] + (floor[i] == '1')  # 累计白砖数量
        for i in range(1, n + 1):
            for j in range(carpetLen * i, m):
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])  # 选择放地毯或不放
        return f[n][-1]  # 返回使用 n 条地毯时的最小未覆盖白砖数量

Explore

在动态规划数组中，f[0][0] 特别初始化为第一个砖块是否为白色（即 floor[0] == '1'），这是因为这代表在不使用任何地毯的情况下，只考虑第一个砖块时的未覆盖白色砖块数。对于 f[0][i]（i > 0），这些值通过累加前面的白色砖块数来计算，从而确保 f[0][i] 正确地表示在不使用地毯覆盖前 i 个砖块时的未覆盖白色砖块数。因此，f[0][0] 是基础值，其余的 f[0][i] 值依赖于 f[0][0] 和后续砖块的颜色进行动态累计。

在动态规划转移方程中使用 min 函数是为了确保在任何给定的 j 砖块位置和 i 条地毯的使用情况下，都能得到最小的未覆盖白色砖块数。min 函数比较两种情况：一种是在 j 位置不放置新地毯，继续保持前一个位置的状态同时加上当前位置是否为白色砖块；另一种是在 j 位置放置一条新地毯，这条地毯覆盖从 j-carpetLen 到 j 的区间，故考虑从 f[i-1][j-carpetLen] 进行转移。这种方法通过枚举所有可能的放置或不放置地毯的情况，确保可以找到所有可能的最佳地毯放置策略，从而实现最优覆盖。

在动态规划中，j 的起始值设置为 carpetLen * i 是基于对问题的一种优化考虑。如果 i 条地毯都用于覆盖，每条地毯长度为 carpetLen，那么最少也需要覆盖 carpetLen * i 长度的砖块。这意味着在 j 小于 carpetLen * i 时，使用 i 条地毯是不可能的，因为地毯的总长度不足以覆盖这么多砖块。因此，从 carpetLen * i 开始计算可以避免无效计算，并保证每次循环中的状态转移都是可行的，从而提高计算效率。