# 2209. Minimum White Tiles After Covering With Carpets
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/
## 思路

(1) 不用carpet ```j```铺第```i```个tile: 那么答案等于```dp[i-1][j]```+判断是否tile ```i```是白色的
(2) 用carpet ```j```铺第```i```个tile: 那么我们一定不希望carpet```j```浪费 所以我们一定把carpet ```j```的末端铺在第```i```个tile 那么答案就等于```dp[i-carpetLen][j-1]```
## Code

class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        floor = '#'+floor;
        int[][] dp = new int[n+1][numCarpets+1];
        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=0; j<=numCarpets; j++){
                dp[i][j] = dp[i-1][j]+(floor.charAt(i)=='0'?0:1);
                if(j>=1) dp[i][j] = Math.min(dp[i][j], i>=carpetLen?dp[i-carpetLen][j-1]:0);
            }
        }
        return dp[n][numCarpets];
    }
}