本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个下标从 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
分析
原理
毛毯尽量不相互覆盖，这样可以覆盖更多的白砖。除非：毛毯放不下了。
如果能够覆盖一张毛毯，那么一定可以覆盖无限毛毯。除非 floor.length 小于carpetLen，否则一定可以覆盖。这种情况题目已经排除了。
计算最多可以盖住多少块白砖，白砖数减去盖住的白砖，就是未盖住的白砖数。
假定新毯子覆盖在[iPre,iPre + carpetLen)，那么前一张毯子不一定在[iPre-carpetLen,iPre)，可以更前。所以执行：
dp[i + 1] = max(dp[i], dp[i + 1]);
执行之前：dp[i]的含义是i的最后一张毯子的尾部，可以覆盖最多砖瓦数。
执行之后：dp[i]的含义是的最后一张毯子的尾部<=i，可以覆盖最多砖瓦数。
时间复杂度
O(n*n)。两层循环，第一层，枚举第i张毛毯。第二层循环，枚举上一次的覆盖位置。
步骤
一，计算白砖数量的前缀和。
二，两层循环。
## 变量解释
| vSum | vSum[i]表示 floor[0,i)中白砖的数量，也就是前i块砖中，白砖的数量 |
| pre | 表示i块毯子，覆盖了[0,i)，能盖住的最多白砖数 |
代码
核心代码
class Solution { public: int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) { //错误想法：如果盖毯子，则毯子的末端一定盖住白砖 //计算最多可以盖住多少块白砖 vector vSum = { 0 };//vSum[i]表示 floor[0,i)中白砖的数量 for (const char& ch : floor) { vSum.emplace_back(vSum.back() + (‘1’ == ch)); } m_c = floor.length(); vector pre (m_c+1,0);//表示i块毯子，覆盖了[0,i)，能盖住的最多白砖数 for (int i = 0; i < numCarpets; i++) { vector dp = pre; for (int iPre = 0; iPre < pre.size(); iPre++) { const int iNew = min(m_c , iPre + carpetLen); dp[iNew] = max(dp[iNew], pre[iPre] + (vSum[iNew]-vSum[iPre])); } for (int i = 0; i < m_c; i++) { dp[i + 1] = max(dp[i], dp[i + 1]); } pre.swap(dp); } return vSum.back() - *std::max_element(pre.begin(),pre.end()); } int m_c; };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; string floor = “10110101”; int numCarpets = 2, carpetLen = 2; int res;
floor = "1110111"; numCarpets = 2, carpetLen = 3; res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen); Assert(0, res); floor = "10110101"; numCarpets = 2, carpetLen = 2; res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen); Assert(2, res); floor = "11111"; numCarpets = 2, carpetLen = 3; res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen); Assert(0, res); //CConsole::Out(res);
}
2023年2月旧代码
class Solution { public: int minimumWhiteTiles(const string floor, const int numCarpets, const int carpetLen) { m_c = floor.length(); //dp[i][j] 已经处理了i块砖，用了j块地毯，最少为覆盖的砖数 vector<vector> dp(m_c+1, vector(numCarpets+1,INT_MAX)); dp[0][0] = 0; for (int brick = 0; brick < m_c; brick++) { for (int iUseCarpets = 0; iUseCarpets <= numCarpets; iUseCarpets++) { const int& iValue = dp[brick][iUseCarpets]; if (INT_MAX == iValue) { continue; } //空一格 dp[brick + 1][iUseCarpets] = min(dp[brick + 1][iUseCarpets], iValue + (‘1’ == floor[brick])); //假定不重叠，如果重叠右移到不重叠，不影响结果 if (numCarpets == iUseCarpets) { continue; } const int iNewBrick = min(brick + carpetLen, m_c); dp[iNewBrick][iUseCarpets + 1] = min(dp[iNewBrick][iUseCarpets + 1], iValue); } } return *std::min_element(dp[m_c].begin(), dp[m_c].end()); } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
