题目描述
你有一块棋盘,棋盘上有一些格子已经坏掉了。你还有无穷块大小为 1 * 2
的多米诺骨牌,你想把这些骨牌不重叠地覆盖在完好的格子上,请找出你最多能在棋盘上放多少块骨牌?这些骨牌可以横着或者竖着放。
输入:n
和 m
代表棋盘的大小;broken
是一个 b * 2
的二维数组,其中每个元素代表棋盘上每一个坏掉的格子的位置。
输出:一个整数,代表最多能在棋盘上放的骨牌数。
样例
输入:n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出:2
解释:我们最多可以放两块骨牌:[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。(见下图)
输入:n = 3, m = 3, broken = []
输出:4
解释:下图是其中一种可行的摆放方式。
限制
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m
算法
(基于轮廓线的状态压缩动态规划 / 插头 DP) $O(nm 2^m)$
- 设状态 $f(i, j, s)$ 表示在 $(i, j)$ 位置且当前轮廓线的状态为 $s$ 时的最大放置数。轮廓线为已决策状态和未决策状态的分界线。可以参考 OI Wiki。
- 这里假设 $i$ 的范围是 $[1, n]$,$j$ 的范围是 $[0, m - 1]$。初始时,$f(0, m - 1, 2^m - 1) = 0$,其余为负无穷待定。
- 对于当前格子 $(i, j)$,枚举上一个格子的轮廓线状态为 $s$。这里上一个格子是 $(i, j - 1)$(如果 $j = 0$,则上一个格子为 $(i - 1, m - 1)$)。
- 如果当前格子为坏掉的格子,则转移 $f(i, j, s + 2^j) = \max(f(i, j, s + 2^j), f(last_i, last_j, s))$。
- 对于非坏掉的格子:
- 如果当前格子可以竖放,则转移 $f(i, j, s + 2^j) = \max(f(i, j, s + 2^j), f(last_i, last_j, s) + 1)$。
- 如果当前格子可以和左边的格子一起横放,则转移 $f(i, j, s + 2^j + 2^{j-1}) = \max(f(i, j, s + 2^j + 2^{j-1}), f(last_i, last_j, s) + 1)$。
- 最终答案为 $\max(f(n, m - 1, s))$。
时间复杂度
- 状态数为 $O(nm2^m)$,每次转移仅需常数的时间,故总时间复杂度为 $O(nm2^m)$。
空间复杂度
- 需要 $O(nm2^m)$ 的额外空间存储坏掉格子的标记数组和动态规划的状态。
C++ 代码
const int N = 9;
const int S = 256;
class Solution {
private:
bool v[N][N];
int f[N][N][S];
public:
int domino(int n, int m, vector<vector<int>>& broken) {
memset(v, false, sizeof(v));
for (const auto &b : broken)
v[b[0] + 1][b[1]] = true;
for (int i = 0; i <= n; i++)
for (int j = 0; j < m; j++)
for (int s = 0; s < (1 << m); s++)
f[i][j][s] = INT_MIN;
f[0][m - 1][(1 << m) - 1] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++) {
int last_i = i, last_j = j - 1;
if (j == 0) {
last_i = i - 1;
last_j = m - 1;
}
for (int s = 0; s < (1 << m); s++) {
if (v[i][j]) {
// 如果是坏掉的格子,直接标记占用
f[i][j][s | (1 << j)] = max(
f[i][j][s | (1 << j)],
f[last_i][last_j][s]
);
continue;
}
// 当前格子不放置
f[i][j][s & (~(1 << j))] = max(
f[i][j][s & (~(1 << j))],
f[last_i][last_j][s]
);
if (((s >> j) & 1) == 0) // 当前格子可以竖放
f[i][j][s | (1 << j)] = max(
f[i][j][s | (1 << j)],
f[last_i][last_j][s] + 1
);
if (j > 0 && ((s >> (j - 1)) & 1) == 0) // 当前格子可以横放
f[i][j][s | (1 << j) | (1 << j - 1)] = max(
f[i][j][s | (1 << j) | (1 << j - 1)],
f[last_i][last_j][s] + 1
);
}
}
int ans = 0;
for (int s = 0; s < (1 << m); s++)
ans = max(ans, f[n][m - 1][s]);
return ans;
}
};