LeetCode 2209.用地毯覆盖后的最少白色砖块：影象化搜索之——深度优先搜索
【LetMeFly】2209.用地毯覆盖后的最少白色砖块：影象化搜索之——深度优先搜索(DFS)力扣标题链接：https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/
给你一个下标从 0 开始的 二进制 字符串 floor ，它表现地板上砖块的颜色。
[*]floor = '0' 表现地板上第 i 块砖块的颜色是 黑色 。
[*]floor = '1' 表现地板上第 i 块砖块的颜色是 白色 。
同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你利用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数量 最小 。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的 最少 数量。
示例 1：
https://i-blog.csdnimg.cn/img_convert/a37188bac190b3f13db176227147101d.png
<b>输入：</b>floor = "10110101", numCarpets = 2, carpetLen = 2
<b>输出：</b>2
<b>解释：</b>
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。
示例 2：
https://i-blog.csdnimg.cn/img_convert/b6934e0d72121251a035a001cd528147.png
<b>输入：</b>floor = "11111", numCarpets = 2, carpetLen = 3
<b>输出：</b>0
<b>解释：</b>
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。
提示：
[*]1 <= carpetLen <= floor.length <= 1000
[*]floor 要么是 '0' ，要么是 '1' 。
[*]1 <= numCarpets <= 1000
解题方法：深度优先搜索(DFS)
写一个函数dfs(n, index)，代表利用n块地毯从下标index开始以后覆盖剩余的最小白色砖块数。
[*] 假如不覆盖当前砖块：
dfs(n, index + 1) + (floor == '1')
[*]可以利用n块地毯覆盖后续砖块，最少有dfs(n, index + 1)块白砖不能覆盖
[*]假如这块砖是白色，则未覆盖白砖数量加一
[*] 假如覆盖当前砖块：
dfs(n - 1, index + 地毯长度)
[*]可以利用n - 1块地毯覆盖从index + 地毯长度开始的砖块
终止条件：当前地毯能覆盖剩下所有砖块。
然后，再利用一个缓存影象化一下就好了。
[*]时间复杂度 O ( n u m C a r p e t s × l e n ( f l o o r ) ) O(numCarpets\times len(floor)) O(numCarpets×len(floor))
[*]空间复杂度 O ( n u m C a r p e t s × l e n ( f l o o r ) ) O(numCarpets\times len(floor)) O(numCarpets×len(floor))
AC代码
C++
/*
* @Author: LetMeFly
* @Date: 2025-02-21 12:25:21
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-21 13:05:12
*/
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;
}
if (n * perLen >= floor.size() - startIndex) {
return cache = 0;
}
int ans = dfs(n, startIndex + 1) + (floor == '1');// 不覆盖
if (n) {
ans = min(ans, dfs(n - 1, startIndex + perLen));// 覆盖
}
return cache = ans;
}
public:
int minimumWhiteTiles(string& floor, int numCarpets, int carpetLen) {
this->floor = move(floor);
this->perLen = carpetLen;
return dfs(numCarpets, 0);
}
};
Python
'''
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 == '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
/*
* @Author: LetMeFly
* @Date: 2025-02-21 13:05:59
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-21 14:39:29
*/
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
/*
* @Author: LetMeFly
* @Date: 2025-02-21 13:06:05
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-21 14:21:55
*/
package main
func dfs_MWTACWC(n, startIndex int, floor string, perLen int, cache mapint) (ans int) {
code := n * 1000 + startIndex
ans, ok := cache
if ok {
return
}
if n * perLen >= len(floor) - startIndex {
cache = 0
return 0
}
ans = dfs_MWTACWC(n, startIndex + 1, floor, perLen, cache)
if floor == '1' {
ans++
}
if n > 0 {
ans = min(ans, dfs_MWTACWC(n - 1, startIndex + perLen, floor, perLen, cache))
}
cache = ans
return
}
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
return dfs_MWTACWC(numCarpets, 0, floor, carpetLen, mapint{})
}
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]