2209. 用地毯覆盖后的最少白色砖块
dp的状态转移还是没理解
class Solution {
public:
int minimumWhiteTiles(string &floor, int n, int carpetLen) {
int m = floor.length();
vector<vector<int>> f(n + 1, vector<int>(m));
f[0][0] = floor[0] % 2;
for (int i = 1; i < m; ++i)
f[0][i] = f[0][i - 1] + floor[i] % 2;
for (int i = 1; i <= n; ++i)
// j < carpetLen 的 f[i][j] 均为 0
for (int j = carpetLen; j < m; ++j)
f[i][j] = min(f[i][j - 1] + floor[j] % 2, f[i - 1][j - carpetLen]);
return f[n][m - 1];
}
};
网友评论