跳转至

2209. 用地毯覆盖后的最少白色砖块

题目描述

给你一个下标从 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

解法

方法一：记忆化搜索

我们设计一个函数 \(\textit{dfs}(i, j)\) 表示从下标 \(i\) 开始，使用 \(j\) 条地毯，最少有多少个白色砖块没有被覆盖。答案即为 \(\textit{dfs}(0, \textit{numCarpets})\)。

对于下标 \(i\)，我们分情况讨论：

  • 如果 \(i \ge n\)，说明已经覆盖完所有砖块，返回 \(0\)；
  • 如果 \(\textit{floor}[i] = 0\)，则不需要使用地毯，直接跳过即可，即 \(\textit{dfs}(i, j) = \textit{dfs}(i + 1, j)\)；
  • 如果 \(j = 0\)，那么我们可以直接利用前缀和数组 \(s\) 计算出剩余未被覆盖的白色砖块的数目，即 \(\textit{dfs}(i, j) = s[n] - s[i]\)；
  • 如果 \(\textit{floor}[i] = 1\)，那么我们可以选择使用地毯覆盖，也可以选择不使用地毯覆盖，取两者的最小值即可，即 \(\textit{dfs}(i, j) = \min(\textit{dfs}(i + 1, j), \textit{dfs}(i + \textit{carpetLen}, j - 1))\)。

记忆化搜索即可。

时间复杂度 \(O(n\times m)\)，空间复杂度 \(O(n\times m)\)。其中 \(n\) 和 \(m\) 分别为字符串 \(\textit{floor}\) 的长度和 \(\textit{numCarpets}\) 的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= n:
                return 0
            if floor[i] == "0":
                return dfs(i + 1, j)
            if j == 0:
                return s[-1] - s[i]
            return min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1))

        n = len(floor)
        s = [0] * (n + 1)
        for i, c in enumerate(floor):
            s[i + 1] = s[i] + int(c == "1")
        ans = dfs(0, numCarpets)
        dfs.cache_clear()
        return ans

 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
class Solution {
    private Integer[][] f;
    private int[] s;
    private int n;
    private int k;

    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        n = floor.length();
        f = new Integer[n][numCarpets + 1];
        s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);
        }
        k = carpetLen;
        return dfs(0, numCarpets);
    }

    private int dfs(int i, int j) {
        if (i >= n) {
            return 0;
        }
        if (j == 0) {
            return s[n] - s[i];
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        if (s[i + 1] == s[i]) {
            return dfs(i + 1, j);
        }
        int ans = Math.min(1 + dfs(i + 1, j), dfs(i + k, j - 1));
        f[i][j] = ans;
        return ans;
    }
}

 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
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<vector<int>> f(n, vector<int>(numCarpets + 1, -1));
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor[i] == '1');
        }
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i >= n) {
                return 0;
            }
            if (j == 0) {
                return s[n] - s[i];
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }
            if (s[i + 1] == s[i]) {
                return dfs(i + 1, j);
            }
            int ans = min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
            f[i][j] = ans;
            return ans;
        };
        return dfs(0, numCarpets);
    }
};

 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
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
    n := len(floor)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, numCarpets+1)
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    s := make([]int, n+1)
    for i, c := range floor {
        s[i+1] = s[i] + int(c-'0')
    }
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i >= n {
            return 0
        }
        if j == 0 {
            return s[n] - s[i]
        }
        if f[i][j] != -1 {
            return f[i][j]
        }
        if s[i+1] == s[i] {
            return dfs(i+1, j)
        }
        ans := min(1+dfs(i+1, j), dfs(i+carpetLen, j-1))
        f[i][j] = ans
        return ans
    }
    return dfs(0, numCarpets)
}

 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
function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
    const n = floor.length;
    const f: number[][] = Array.from({ length: n }, () => Array(numCarpets + 1).fill(-1));
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
    }
    const dfs = (i: number, j: number): number => {
        if (i >= n) {
            return 0;
        }
        if (j === 0) {
            return s[n] - s[i];
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        if (s[i + 1] === s[i]) {
            return dfs(i + 1, j);
        }
        const ans = Math.min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
        f[i][j] = ans;
        return ans;
    };
    return dfs(0, numCarpets);
}

评论