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：

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

复制代码

示例 2：

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

复制代码

 
提示：

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

解题方法：深度优先搜索(DFS)

写一个函数dfs(n, index)，代表利用n块地毯从下标index开始以后覆盖剩余的最小白色砖块数。

• 假如不覆盖当前砖块：
  dfs(n, index + 1) + (floor[index] == '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++

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-02-21 12:25:21
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-02-21 13:05:12
6. */
7. class Solution {
8. private:
9.     unordered_map<int, int> cache;
10.     string floor;
11.     int perLen;
13.     int dfs(int n, int startIndex) {
14.         int code = n * 1000 + startIndex;
15.         if (cache.count(code)) {
16.             return cache[code];
17.         }
18.         if (n * perLen >= floor.size() - startIndex) {
19.             return cache[code] = 0;
20.         }
21.         int ans = dfs(n, startIndex + 1) + (floor[startIndex] == '1');  // 不覆盖
22.         if (n) {
23.             ans = min(ans, dfs(n - 1, startIndex + perLen));  // 覆盖
24.         }
25.         return cache[code] = ans;
26.     }
27. public:
28.     int minimumWhiteTiles(string& floor, int numCarpets, int carpetLen) {
29.         this->floor = move(floor);
30.         this->perLen = carpetLen;
31.         return dfs(numCarpets, 0);
32.     }
33. };

复制代码

Python

1. '''
2. Author: LetMeFly
3. Date: 2025-02-21 13:05:56
4. LastEditors: LetMeFly.xyz
5. LastEditTime: 2025-02-21 13:11:13
6. '''
7. from functools import cache
10. class Solution:
11.     @cache
12.     def dfs(self, n: int, startIndex: int) -> int:
13.         if n * self.perLen >= len(self.floor) - startIndex:
14.             return 0
15.         ans = self.dfs(n, startIndex + 1) + (self.floor[startIndex] == '1')
16.         if n:
17.             ans = min(ans, self.dfs(n - 1, startIndex + self.perLen))
18.         return ans
19.    
20.     def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
21.         self.floor = floor
22.         self.perLen = carpetLen
23.         return self.dfs(numCarpets, 0)

复制代码

Java

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-02-21 13:05:59
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-02-21 14:39:29
6. */
7. import java.util.Map;
8. import java.util.HashMap;
10. class Solution {
11.     private String floor;
12.     private int perLen;
13.     private Map<Integer, Integer> cache = new HashMap<>();
15.     private int dfs(int n, int index) {
16.         int code = n * 1000 + index;
17.         if (cache.containsKey(code)) {
18.             return cache.get(code);
19.         }
20.         if (n * perLen >= floor.length() - index) {
21.             cache.put(code, 0);
22.             return 0;
23.         }
24.         int ans = dfs(n, index + 1);
25.         if (floor.charAt(index) == '1') {
26.             ans++;
27.         }
28.         if (n > 0) {
29.             ans = Math.min(ans, dfs(n - 1, index + perLen));
30.         }
31.         cache.put(code, ans);
32.         return ans;
33.     }
35.     public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
36.         this.floor = floor;
37.         perLen = carpetLen;
38.         return dfs(numCarpets, 0);
39.     }
40. }

复制代码

Go

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-02-21 13:06:05
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-02-21 14:21:55
6. */
7. package main
9. func dfs_MWTACWC(n, startIndex int, floor string, perLen int, cache map[int]int) (ans int) {
10.     code := n * 1000 + startIndex
11.     ans, ok := cache[code]
12.     if ok {
13.         return
14.     }
15.     if n * perLen >= len(floor) - startIndex {
16.         cache[code] = 0
17.         return 0
18.     }
19.     ans = dfs_MWTACWC(n, startIndex + 1, floor, perLen, cache)
20.     if floor[startIndex] == '1' {
21.         ans++
22.     }
23.     if n > 0 {
24.         ans = min(ans, dfs_MWTACWC(n - 1, startIndex + perLen, floor, perLen, cache))
25.     }
26.     cache[code] = ans
27.     return
28. }
30. func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
31.     return dfs_MWTACWC(numCarpets, 0, floor, carpetLen, map[int]int{})
32. }

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  千篇源码题解已开源

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。