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

发表于 分类于 阅读次数： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        # 【定义状态】dp[i][j]：使用i条地毯覆盖长度为j的砖块，没被覆盖的白色砖块的最少数目
        dp = [[0]*(len(floor)+1) for _ in range(numCarpets+1)]

        for i in range(numCarpets+1):
            for j in range(1, len(floor)+1):
                if i == 0:
                    # 未使用地毯时，没被覆盖的白色砖块 即 地板上白色砖块的数目
                    dp[i][j] = dp[i][j-1] + int(floor[j-1])
                    continue

                # 使用地毯时，分2种情况讨论：
                # （1）第j块砖块没被覆盖时，没被覆盖的白色砖块 = 使用i条地毯覆盖长度为j-1的砖块时的最少白块数目+第j块是否为白块
                # （2）第j块砖块被覆盖时，没被覆盖的白色砖块 = 使用i-1条地毯覆盖长度为j-carpetLen的砖块
                #    （若j<=carpetLen，则j块砖全部被覆盖，没被覆盖的白色砖块为0）
                dp[i][j] = min(
                    dp[i][j-1] + int(floor[j-1]),
                    j > carpetLen and dp[i-1][j-carpetLen] or 0
                )

        return dp[numCarpets][len(floor)]