問題背景

給你一個下標從 $0$ 開始的 二進制 字符串 $floor$，它表示地板上磚塊的顏色。

• $floor[i]$ 為 ‘0’ 表示地板上第 $i$ 塊磚塊的顏色是 黑色 。
• $floor[i]$ 為’1’ 表示地板上第 $i$ 塊磚塊的顏色是 白色 。

同時給你 $numCarpets$ 和 $carpetLen$。你有 $numCarpets$ 條 黑色 的地毯，每一條 黑色 的地毯長度都為 $carpetLen$ 塊磚塊。請你使用這些地毯去覆蓋磚塊，使得未被覆蓋的剩余 白色 磚塊的數目 最小 。地毯相互之間可以覆蓋。
請你返回沒被覆蓋的白色磚塊的 最少 數目。

數據約束

• $1\le carpetLen\le floor.length\le 1000$
• $floor[i]$要么是 ‘0’ ，要么是 ‘1’ 。
• $1\le numCarpets\le 1000$

解題過程

比較標準的動態規劃模板題，關鍵是定義清楚狀態，這里用$i$表示剩余的地毯數量，$j$表示剩余的磚塊數量。
空間優化的做法沒完全理解，先不要求。

具體實現

遞歸

class Solution {public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {int n = floor.length();int[][] memo = new int[numCarpets + 1][n];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(numCarpets, n - 1, floor.toCharArray(), memo, carpetLen);}private int dfs(int i, int j, char[] floor, int[][] memo, int carpetLen) {if (j < carpetLen * i) {return 0;}if (memo[i][j] != -1) {return memo[i][j];}int res = dfs(i, j - 1, floor, memo, carpetLen) + floor[j] - '0';if (i > 0) {res = Math.min(res, dfs(i - 1, j - carpetLen, floor, memo, carpetLen));}return memo[i][j] = res;}
}

遞推

class Solution {public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {char[] chF = floor.toCharArray();int n = chF.length;int[][] dp = new int[numCarpets + 1][n];dp[0][0] = chF[0] - '0';for (int j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + chF[j] - '0';}for (int i = 1; i <= numCarpets; i++) {for (int j = carpetLen * i; j < n; j++) {dp[i][j] = Math.min(dp[i][j - 1] + chF[j] - '0', dp[i - 1][j - carpetLen]);}}return dp[numCarpets][n - 1];}
}