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

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 536 阅读时长 ≈ 2 分钟

考点

  • 划分DP
  • 区间重叠

思路

划分DP裸题，f[j][i]设为前i个数放了j个毯子，那么对于第i个数，有放和不放两种情况，讨论即可

本题的难点在于毯子可以叠加，而我们的划分DP从来都是区间相互隔离开的

假设长度为5，毯子长度为3，按照我们之前的写法，第1、第2个都是不能放毯子的，只有第3个开始才有空间能放

但实际上，只要有大于等于2次放毯子的机会，不仅第3、4、5也可以放毯子，第1、2、3也应该放毯子

仔细观察发现，叠加这一操作只会影响当下标i小于carpetLen，且1 ~ carpetLen这个区间有机会放毯子的时候

举个例子

1
2
3
长度为5, 毯子长度为3
f[0][i]是1~i的'1'的个数前缀和, 因为没有盖毯子机会
而f[j>=1][1~carpenLen-1]全部赋值为0即可, 因为该区间只要有至少一次覆盖机会, 就能全部覆盖

AC代码如下：

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
class Solution {
 public:
  int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
    int n = floor.size();
    // f[j][i]: 前i个铺了j个地毯
    int f[1005][1005];
    memset(f, 0, sizeof(f));
    for (int i = 1, s = 0; i <= n; ++i) {
      s += floor[i - 1] == '1';
      f[0][i] = s;
    }
    for (int j = 1; j <= numCarpets; ++j) {
      for (int i = 1; i <= n; ++i) {
        // i不铺地毯
        f[j][i] = f[j][i - 1] + (floor[i - 1] == '1');
        // i铺地毯
        if (i >= carpetLen)
          f[j][i] = min(f[j][i], f[j - 1][i - carpetLen]);
        else
          f[j][i] = 0;
      }
    }
    return f[numCarpets][n];
  }
};

当然也可以滚动数组，降低常数：

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
class Solution {
 public:
  int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
    int n = floor.size();
    // f[j][i]: 前i个铺了j个地毯
    int f[2][1005];
    memset(f, 0, sizeof(f));
    for (int i = 1, s = 0; i <= n; ++i) {
      s += floor[i - 1] == '1';
      f[0 & 1][i] = s;
    }
    for (int j = 1; j <= numCarpets; ++j) {
      for (int i = 1; i <= n; ++i) {
        // i不铺地毯
        f[j & 1][i] = f[j & 1][i - 1] + (floor[i - 1] == '1');
        // i铺地毯
        if (i >= carpetLen)
          f[j & 1][i] = min(f[j & 1][i], f[j - 1 & 1][i - carpetLen]);
        else
          f[j & 1][i] = 0;
      }
    }
    return f[numCarpets & 1][n];
  }
};