Leetcode Problem 2209. Minimum White Tiles After Covering With Carpets

2209. Minimum White Tiles After Covering With Carpets

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D array dp with dimensions [floor.length + 1][numCarpets + 1] and fill it with zeros.
  2. Iterate over the length of the floor from 1 to n (inclusive).
  3. For each position i, iterate over the number of carpets from 0 to numCarpets (inclusive).
  4. Calculate the number of white tiles if we 'jump' over the current tile: jump = dp[i - 1][k] + (floor[i - 1] == '1' ? 1 : 0).
  5. Calculate the number of white tiles if we 'cover' the current tile with a carpet: cover = k > 0 ? dp[max(0, i - carpetLen)][k - 1] : infinity.
  6. Update the current state with the minimum of 'jump' and 'cover': dp[i][k] = min(jump, cover).
  7. After filling the dp table, return the value of dp[n][numCarpets] as the minimum number of white tiles visible.
UML Thumbnail

Top-Down Dynamic Programming with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...