当前位置：首页 > article >正文

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

article 2025/2/22 19:51:54

【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 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

/*
 * @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 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{})
}