LeetCode 2209.用地毯覆盖后的最少白色砖块：记忆化搜索之—

LeetCode 2209.用地毯覆盖后的最少白色砖块：记忆化搜索之——深度优先搜索(DFS)

【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 <= 1000
floor[i] 要么是 '0' ，要么是 '1' 。
1 <= numCarpets <= 1000

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

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

如果不覆盖当前砖块：

dfs(n, index + 1) + (floor[index] == '1')
1. 可以使用n块地毯覆盖后续砖块，最少有dfs(n, index + 1)块白砖不能覆盖
2. 如果这块砖是白色，则未覆盖白砖数量加一
如果覆盖当前砖块：

dfs(n - 1, index + 地毯长度)
1. 可以使用n - 1块地毯覆盖从index + 地毯长度开始的砖块

终止条件：当前地毯能覆盖剩下所有砖块。

然后，再使用一个缓存记忆化一下就好了。

时间复杂度 $O(numCarpets\times len(floor))$
空间复杂度 $O(numCarpets\times 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[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

'''
Author: LetMeFly
Date: 2025-02-21 13:05:56
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-21 13:11:13
'''
from functools import cacheclass Solution:@cachedef dfs(self, n: int, startIndex: int) -> int:if n * self.perLen >= len(self.floor) - startIndex:return 0ans = self.dfs(n, startIndex + 1) + (self.floor[startIndex] == '1')if n:ans = min(ans, self.dfs(n - 1, startIndex + self.perLen))return ansdef minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:self.floor = floorself.perLen = carpetLenreturn 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 mainfunc dfs_MWTACWC(n, startIndex int, floor string, perLen int, cache map[int]int) (ans int) {code := n * 1000 + startIndexans, ok := cache[code]if ok {return}if n * perLen >= len(floor) - startIndex {cache[code] = 0return 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] = ansreturn
}func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {return dfs_MWTACWC(numCarpets, 0, floor, carpetLen, map[int]int{})
}