力扣每日一题----2209. 用地毯覆盖后的最少白色砖块

? ? ? ? //这题我们先考虑的是如何从所有覆盖方案中找到最少数目的方案
? ? ? ? //一个暴搜就是暴力解法，比如有1000块，那么每次枚举填的起始位置的
? ? ? ? //话就是很大的时间复杂度了，就算用记忆化搜索也没用
? ? ? ? //那么动态规划可行吗，可行的，我们先来分析一下
? ? ? ? //枚举第一块的时候，我们有1000中选择，枚举第二块的时候，因为可以重复覆盖
? ? ? ? //又有1000种选择，那么枚举第二快的时候，第二块的状态是由枚举第一块的状态
? ? ? ? //转移过来的
? ? ? ? //f[i][j] = min(f[i][j],f[i - 1][1 ~ m] + ?);
? ? ? ? //目前根据前面的说明，我们很显然知道f[i][j]是枚举第i块放到j为起始位置时的白砖块最少数目
? ? ? ? //那么我们怎么知道f[i - 1][1 ~ m]时的状态呢？
? ? ? ? //用个数组保存下来放置第几块哪个位置的状态，可以用状态压缩来解决状态
? ? ? ? //那么我们现在有了状态数组s[i][j]，但是我们还要怎么去计算可以减少多少个白色砖块
? ? ? ? //然后发现，状态数组怎么计算呢？减少多少个白色砖块呢？这就成了难点了，我们也没有
? ? ? ? //办法让他在O(1)或者logn的时间内完成。那么该处理方法不是很好。因为我们每次
? ? ? ? //都要从j这个初始位置往后去计算减少多少个白色砖块，最坏的的时候，就变成o(N^3)，变成
? ? ? ? //n^3也是因为没有好的处理方法去处理他
? ? ? ? //我们在状态转移过程的时候，主要是要去掉后面那个?部分的计算过程变成O(1),或者变成O(logn)这种
? ? ? ? //常数级别的
? ? ? ? //那么我们现在再去仔细思考一下发现，铺第二块以j为结尾，也能把所有方案存下来
? ? ? ? //那么此时我们的状态定义就变成了f[i][j]是枚举第i块放上之后以j为结尾位置时的白砖块最少数目
? ? ? ? //1.f[i][j] = min(f[i][j],f[i - 1][j - carpetlen]);
? ? ? ? //那如果不放呢？我们怎么转移过来呢？
? ? ? ? //我们就从前面更新过的转移过来就行，如果第j位是1的话需要+1
? ? ? ? //2.f[i][j] = min(f[i][j],f[i][j - 1] + (a[j] == '1' ? 1: 0));
? ? ? ? //那么我们的第一个状态怎么解释呢？这里其实我们还用到了一个贪心
? ? ? ? //怎么贪以第j个位置为结尾的话，那么必然是贪以j - carpetlen这个位置是最好的，可以确保覆盖的白色
? ? ? ? //砖块最多，其他地方，虽然我们根据状态定义是可以知道从j - carpetlen这个位置为结尾转移过来的
? ? ? ? //但是我们在想的时候肯定不是这么想的，我们肯定是想第二次是恰好拼接到一下好，还是往前面一点同时
? ? ? ? //覆盖一下拼接好，我们肯定是恰好拼接的好

? ? ? ?本题还有一个很重要的点就是第二个状态转移，为什么要前一列转移过来呢？

? ? ? ?因为不放地毯的话，假设两段之间有一段空的，那么空的那部分和放了第一个地毯

? ? ? ?的状态转移方程是一样的，所以可以直接转过来判断当前位是否为1

class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) 
    {
        int m = floor.size();
        int f[numCarpets + 10][m + 10];
        memset(f,0,sizeof(f));
        //第0层不需要转移，我们直接初始化
        f[0][0] = (floor[0] == '1');
        for(int i = 1;i < m;i++) f[0][i] = f[0][i - 1] + (floor[i] == '1');


        for(int i = 1;i <= numCarpets;i++)
        {
           for(int j = 1;j <= m;j++)
           {
              if(j - carpetLen >= 0)
              f[i][j] = min(f[i - 1][j - carpetLen],f[i][j - 1] + (floor[j] == '1'));
           }    
        }

        return f[numCarpets][m - 1];
    }
};