织梦门户网站模板/促销方法100种

问题背景

给你一个下标从 $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];}
}