here is my thought
this is a dp problem, in order to get min white tiles on floor[0:n - 1]
define dp[i][j] means the min white tiles on floor[i:n - 1] with j carpets
we can scan from left to right, when we meet a white tile, eg i-th element, we can choose cover it or not.
- if we cover it. in order to cover most white tiles, we put one carpet from i-th, so it can cover floor[i : i + carpetLen - 1], in this case, the min white tiles is dp[i + carpetLen][j - 1], right ? because we has cover floor[i : i + carpetLen - 1]
- if we don't cover it, we move to i+1-th element, in this case, the min white tiles is dp[i + 1][j] + 1, right ? because this i-th element we didn't cover
so, dp[i][j] = Math.min( dp[i + carpetLen][j - 1], dp[i + 1][j] + 1)
here is my code
class Solution {
private int[] sum;
private int n;
public int minimumWhiteTiles(String floor, int cnt, int len) {
char[] cs = floor.toCharArray();
n = cs.length;
sum = new int[n];
sum[0] = cs[0] - '0';
for (int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + (cs[i] - '0');
}
int[][] dp = new int[n][cnt + 1];
for (int[] d : dp) {
Arrays.fill(d, -1);
}
return dfs(cs, 0, dp, cnt, len);
}
private int dfs(char[] cs, int index, int[][] dp, int cnt, int len) {
while (index < n && cs[index] == '0') {
index++;
}
if (index >= n) {
return 0;
}
if (cnt == 0) {
return sum[n - 1] - sum[index - 1];
}
if (dp[index][cnt] != -1) {
return dp[index][cnt];
}
// System.out.println(index + "," + cnt);
int cover = dfs(cs, index + len, dp, cnt - 1, len);
int uncover = dfs(cs, index + 1, dp, cnt, len);
int res = Math.min(cover, uncover + 1);
dp[index][cnt] = res;
return res;
}
}
