【LetMeFly】2209.用地毯覆盖后的最少白色砖块：记忆化搜索之——深度优先搜索(DFS)
力扣题目链接：https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/
给你一个下标从 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 <= 1000floor[i] 要么是 '0' ，要么是 '1' 。1 <= numCarpets <= 1000
解题方法：深度优先搜索(DFS)
写一个函数dfs(n, index)，代表使用n块地毯从下标index开始往后覆盖剩余的最小白色砖块数。
终止条件：当前地毯能覆盖剩下所有砖块。
然后，再使用一个缓存记忆化一下就好了。
- 时间复杂度$O(numCarpets\times len(floor))$
- 空间复杂度$O(numCarpets\times len(floor))$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
private:
unordered_map<int, int> cache;
string floor;
int perLen;
int dfs(int n, int startIndex) {
int code = n * 1000 + startIndex;
if (cache.count(code)) {
return cache[code];
}
if (n * perLen >= floor.size() - startIndex) {
return cache[code] = 0;
}
int ans = dfs(n, startIndex + 1) + (floor[startIndex] == '1');
if (n) {
ans = min(ans, dfs(n - 1, startIndex + perLen));
}
return cache[code] = ans;
}
public:
int minimumWhiteTiles(string& floor, int numCarpets, int carpetLen) {
this->floor = move(floor);
this->perLen = carpetLen;
return dfs(numCarpets, 0);
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| '''
Author: LetMeFly
Date: 2025-02-21 13:05:56
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-21 13:11:13
'''
from functools import cache
class Solution:
@cache
def dfs(self, n: int, startIndex: int) -> int:
if n * self.perLen >= len(self.floor) - startIndex:
return 0
ans = self.dfs(n, startIndex + 1) + (self.floor[startIndex] == '1')
if n:
ans = min(ans, self.dfs(n - 1, startIndex + self.perLen))
return ans
def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
self.floor = floor
self.perLen = carpetLen
return self.dfs(numCarpets, 0)
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.util.Map;
import java.util.HashMap;
class Solution {
private String floor;
private int perLen;
private Map<Integer, Integer> cache = new HashMap<>();
private int dfs(int n, int index) {
int code = n * 1000 + index;
if (cache.containsKey(code)) {
return cache.get(code);
}
if (n * perLen >= floor.length() - index) {
cache.put(code, 0);
return 0;
}
int ans = dfs(n, index + 1);
if (floor.charAt(index) == '1') {
ans++;
}
if (n > 0) {
ans = Math.min(ans, dfs(n - 1, index + perLen));
}
cache.put(code, ans);
return ans;
}
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
this.floor = floor;
perLen = carpetLen;
return dfs(numCarpets, 0);
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
package main
func dfs_MWTACWC(n, startIndex int, floor string, perLen int, cache map[int]int) (ans int) {
code := n * 1000 + startIndex
ans, ok := cache[code]
if ok {
return
}
if n * perLen >= len(floor) - startIndex {
cache[code] = 0
return 0
}
ans = dfs_MWTACWC(n, startIndex + 1, floor, perLen, cache)
if floor[startIndex] == '1' {
ans++
}
if n > 0 {
ans = min(ans, dfs_MWTACWC(n - 1, startIndex + perLen, floor, perLen, cache))
}
cache[code] = ans
return
}
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
return dfs_MWTACWC(numCarpets, 0, floor, carpetLen, map[int]int{})
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源