↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-2209 用地毯覆盖后的最少白色砖块 #

Solution 1 #

记 $dp[i][j]$ 代表在 $floor[0:i]$ 这一段使用 $j$ 条地毯覆盖后的最少白色砖块数. 状态转移考虑是否在最右侧放置地毯即可. 代码如下:

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        dp = [[0] * (numCarpets + 1) for _ in range(n)]
        dp[0][0] = floor[0] == '1'
        for i in range(1, n):
            for j in range(0, numCarpets + 1):
                dp[i][j] = dp[i - 1][j] + (floor[i] == '1')
                if j > 0:
                    if i >= carpetLen:    
                        dp[i][j] = min(dp[i][j], dp[i - carpetLen][j - 1])
                    else:
                        dp[i][j] = min(dp[i][j], 0)
        return dp[n - 1][numCarpets]