Leetcode 2209

Link: 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 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的最少数目。

核心算法和原理

类似背包问题：考虑选或不选

重叠子问题：对于(j块地毯，覆盖到floor[i])，如果覆盖则转变为(j - 1, floor[i - carpetLen])，否则转变为(j, floor[i - 1])

dp[i][j]表示「使用i块地毯覆盖从头到floor[j]的地板，这i块地板中未被覆盖的白色砖块的最小数量」，则状态转移：

第三种情况解释：前面i * len块地板可以被j块地毯全部覆盖，故直接为0，向上打表时直接从i * len开始遍历即可

essentials: 空间优化时，由于同时用到方向相同的「上次遍历的结果」和「本次遍历的结果」（画一下状态转移方向即可明白），这种情况可以每次用临时数组保存新值，一遍之后用std::move 把引用转移到原数组，即可在不复制资源的情况下同时保留「上次遍历结果」和「本次迄今为止的结果」

代码


class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<int> dp(n);  // set to 0 default

       
        dp[0] = floor[0] - '0';
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + floor[i] - '0';
        }

        for (int i = 1; i <= numCarpets; i++) {
            vector<int> ndp(n);
            for (int j = i * carpetLen; j < n; j++) {
                // 前面的位置全部被填满，故j < i * len时，dp[j] = 0
                ndp[j] = min(dp[j - carpetLen], ndp[j - 1] + floor[j] - '0');
            }
            dp = move(ndp);
        }

        return dp[n - 1];
    }
};