20250221力扣每日一题

知识点

static constexpr int INF = 0x3f3f3f3f;

static关键字表示这个常量INF是静态的；静态成员属于类本身，无论创建多少个类的实例，INF都只有一个实例，并且可以在类的所有对象中使用
constexpr关键字表示这个常量是一个编译时的常量，INF的值在编译时就已经确定
int INF = 0x3f3f3f3f在算法竞赛常被用于“无穷大”的替代值

解题思路

求地毯无法覆盖的白色方块的最小数量
因为不用考虑左侧已铺设的地毯的位置，只需要关注剩余地毯的数量，所以可以考虑使用动态规划
动态规划从两个大方向考虑：
- 状态表示：d[i][j]表示在前i个砖块上用了j块地毯后，最少的剩余的白色方块还有多少
  - 集合：在前i个砖块上用了j块地毯之后，剩余白色方块的数量
  - 属性：最小值
- 状态计算：将d[i][j]集合进行分类，按照当前方砖是否被地毯覆盖来分类
  - 当前方砖被地毯覆盖：d[max(0, i - carpetLen)][j - 1]
  - 当前方砖未被地毯覆盖：d[i - 1][j] + (floor[i] == '1')
    - 如果当前方砖为白色砖块，那么就要++
获得转移方程

\[d[i][j]=min(d[i - 1][j] + (floor[i] == \text{'1'}),d[i - carpetLen][j - 1])\]

实现代码

class Solution {
public:
    static constexpr int INF = 0x3f3f3f3f;
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<vector<int>> d(n + 1, vector<int>(numCarpets + 1, INF));
        for(int j = 0; j <= numCarpets; j ++){
            d[0][j] = 0;
        }

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

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= numCarpets; j ++){
                d[i][j] = d[i - 1][j] + (floor[i - 1] == '1');
                d[i][j] = min(d[i][j], d[max(0, i - carpetLen)][j - 1]);
            }
        }


        return d[n][numCarpets];
    }
};

知识点

解题思路

实现代码

Enjoy Reading This Article?