2209-用地毯覆盖后的最少白色砖块

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个下标从 ** 0** 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

  • floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
  • floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色
的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小
。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

示例 1：

**输入：** floor = "10110101", numCarpets = 2, carpetLen = 2
**输出：** 2
**解释：**
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2：

**输入：** floor = "11111", numCarpets = 2, carpetLen = 3
**输出：** 0
**解释：**
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。

提示：

  • 1 <= carpetLen <= floor.length <= 1000
  • floor[i] 要么是 '0' ，要么是 '1' 。
  • 1 <= numCarpets <= 1000

提示 1

思考方向？

看到题目给的数据范围，先想想能否用 DP 做出来。（DP 可以认为是一种更高级的暴力）

提示 2

如何定义 DP 的状态？

一般来说，题目给了什么就用什么定义：地板长度和地毯个数。而地毯长度更适合去划分状态。

只用地板长度一个维度够吗？

不够，状态定义没有体现出所使用的地毯的个数。因此需要两个维度。

提示 3

状态的值及其转移如何设计？

一般来说，题目求什么就定义什么：定义 f[i][j] 表示用 i 条地毯覆盖前 j 块板砖时，没被覆盖的白色砖块的最少数目。

转移时可以考虑是否使用第 i 条地毯，且其末尾覆盖第 j 块板砖：（为什么是末尾？因为 f[i][j] 的定义是前 j 块板砖，覆盖 j 后面的板砖完全是在浪费地毯长度）

  • 不使用：f[i][j] = f[i][j-1] + [\textit{floor}[j]=\text{`1’}]；
  • 使用：f[i][j] = f[i-1][j-\textit{carpetLen}]。

取二者最小值，即

f[i][j] = \min(f[i][j-1] + [\textit{floor}[j]=\text{`1’}],f[i-1][j-\textit{carpetLen}])

注意 i=0 的时候只能不使用，需要单独计算。

最后答案为 f[\textit{numCarpets}][\textit{floor.length}-1]。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 剪枝
        f = [[0] * m for _ in range(n + 1)]
        f[0][0] = (floor[0] == '1')
        for i in range(1, m):
            f[0][i] = f[0][i - 1] + (floor[i] == '1')
        for i in range(1, n + 1):
            # j < carpetLen * i 的 f[i][j] 均为 0
            for j in range(carpetLen * i, m):
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])
        return f[n][-1]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumWhiteTiles(String floor, int n, int carpetLen) {
        var m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        var f = new int[n + 1][m];
        f[0][0] = floor.charAt(0) % 2;
        for (var i = 1; i < m; ++i)
            f[0][i] = f[0][i - 1] + floor.charAt(i) % 2;
        for (var i = 1; i <= n; ++i)
            // j < carpetLen * i 的 f[i][j] 均为 0
            for (var j = carpetLen * i; j < m; ++j)
                f[i][j] = Math.min(f[i][j - 1] + floor.charAt(j) % 2, f[i - 1][j - carpetLen]);
        return f[n][m - 1];
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumWhiteTiles(string &floor, int n, int carpetLen) { // 默认代码没加引用，这里补上
        int m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        vector<vector<int>> f(n + 1, vector<int>(m));
        f[0][0] = (floor[0] == '1');
        for (int i = 1; i < m; ++i)
            f[0][i] = f[0][i - 1] + (floor[i] == '1');
        for (int i = 1; i <= n; ++i)
            // j < carpetLen * i 的 f[i][j] 均为 0
            for (int j = carpetLen * i; j < m; ++j)
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen]);
        return f[n][m - 1];
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minimumWhiteTiles(floor string, n, carpetLen int) int {
	m := len(floor)
	if n*carpetLen >= m { // 剪枝
		return 0
	}
	f := make([][]int, n+1)
	f[0] = make([]int, m)
	f[0][0] = int(floor[0] & 1)
	for i := 1; i < m; i++ {
		f[0][i] = f[0][i-1] + int(floor[i]&1)
	}
	for i := 1; i <= n; i++ {
		f[i] = make([]int, m)
		// j < carpetLen * i 的 f[i][j] 均为 0
		for j := carpetLen * i; j < m; j++ {
			f[i][j] = min(f[i][j-1]+int(floor[j]&1), f[i-1][j-carpetLen])
		}
	}
	return f[n][m-1]
}

func min(a, b int) int { if a > b { return b }; return a }

也可以用滚动数组压缩掉第一维：

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 剪枝
        pre, f = [0] * m, [0] * m
        pre[0] = (floor[0] == '1')
        for i in range(1, m):
            pre[i] = pre[i - 1] + (floor[i] == '1')
        for i in range(1, n + 1):
            # j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0
            for j in range(carpetLen * i, m):
                f[j] = min(f[j - 1] + (floor[j] == '1'), pre[j - carpetLen])
            pre, f = f, pre
        return pre[-1]
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minimumWhiteTiles(String floor, int n, int carpetLen) {
        var m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        var pre = new int[m];
        var f = new int[m];
        pre[0] = floor.charAt(0) % 2;
        for (var i = 1; i < m; ++i)
            pre[i] = pre[i - 1] + floor.charAt(i) % 2;
        for (var i = 1; i <= n; ++i) {
            // j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0;
            for (var j = carpetLen * i; j < m; ++j)
                f[j] = Math.min(f[j - 1] + floor.charAt(j) % 2, pre[j - carpetLen]);
            var tmp = f;
            f = pre;
            pre = tmp;
        }
        return pre[m - 1];
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumWhiteTiles(string &floor, int n, int carpetLen) { // 默认代码没加引用，这里补上
        int m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        vector<int> pre(m), f(m);
        pre[0] = (floor[0] == '1');
        for (int i = 1; i < m; ++i)
            pre[i] = pre[i - 1] + (floor[i] == '1');
        for (int i = 1; i <= n; ++i) {
            // j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0;
            for (int j = carpetLen * i; j < m; ++j)
                f[j] = min(f[j - 1] + (floor[j] == '1'), pre[j - carpetLen]);
            swap(pre, f);
        }
        return pre[m - 1];
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func minimumWhiteTiles(floor string, n, carpetLen int) int {
	m := len(floor)
	if n*carpetLen >= m { // 剪枝
		return 0
	}
	pre := make([]int, m)
	f := make([]int, m)
	pre[0] = int(floor[0] & 1)
	for i := 1; i < m; i++ {
		pre[i] = pre[i-1] + int(floor[i]&1)
	}
	for i := 1; i <= n; i++ {
		// j < carpetLen * i 的 f[i][j] 均为 0
		f[carpetLen*i-1] = 0
		for j := carpetLen * i; j < m; j++ {
			f[j] = min(f[j-1]+int(floor[j]&1), pre[j-carpetLen])
		}
		pre, f = f, pre
	}
	return pre[m-1]
}

func min(a, b int) int { if a > b { return b }; return a }

复杂度分析

  • 时间复杂度：O(nm)，这里 m 是 floor 的长度。
  • 空间复杂度：O(m)。

相似题目

 Comments
On this page
2209-用地毯覆盖后的最少白色砖块