Broken profile DP: как посчитать число замощений доски n×m доминошками 1×2?
Доска $n \times m$ ($n \le 16$, $m$ может быть больше). Сколько способов полностью замостить её доминошками $1\times 2$ (горизонтальными и вертикальными)? Слышал про «ДП по профилю» и «broken profile», но не понимаю, что такое профиль и как делать переход по одной клетке.
2 ответа
Broken profile DP — обходим клетки по столбцам (или строкам) одну за другой, а состояние = профиль — битовая маска из n бит, описывающая «границу» между уже заполненной и ещё пустой частью. Бит j профиля = «клетка в строке j на границе уже занята выступом доминошки слева».
Идём по клеткам (col, row) в порядке столбец-за-столбцом. Для текущей клетки три варианта: она уже занята (из предыдущего хода), поставить горизонтальную доминошку (займёт текущую и клетку справа), поставить вертикальную (текущую и снизу).
int n, m; // n <= 16 строк, m столбцов
// dp[mask] = число замощений до текущей клетки с профилем mask
vector<long long> dp(1 << n, 0), ndp;
dp[0] = 1;
for (int col = 0; col < m; ++col)
for (int row = 0; row < n; ++row) {
ndp.assign(1 << n, 0);
for (int mask = 0; mask < (1 << n); ++mask) {
if (dp[mask] == 0) continue;
if (mask & (1 << row)) { // клетка уже занята
ndp[mask ^ (1 << row)] += dp[mask]; // снимаем бит, идём дальше
} else {
// вертикальная доминошка: занимает (row) и (row+1)
if (row + 1 < n && !(mask & (1 << (row + 1))))
ndp[mask | (1 << (row + 1))] += dp[mask];
// горизонтальная: занимает текущую и клетку в след. столбце
if (col + 1 < m)
ndp[mask | (1 << row)] += dp[mask];
}
}
dp = ndp;
}
// ответ dp[0]
Сложность: клеток $n\cdot m$, на каждой перебор $2^n$ профилей → время $O(n \cdot m \cdot 2^n)$, память $O(2^n)$. Для $n=16$: $2^{16}=65536$, умножаем на $n\cdot m$ — заходит при разумных $m$.
Почему «broken» (ломаный) профиль, а не «прямой»? В прямом профиле переход идёт по целому столбцу сразу — перебор пар совместимых масок столбцов, $O(m \cdot 2^n \cdot 2^n)$ или $O(m\cdot 3^n)$ через перебор подмасок, что для $n=16$ медленнее. Broken profile двигает границу по одной клетке, отсюда чистый $O(n m 2^n)$ и простые переходы (три случая на клетку).
Грабля: всегда обнуляй ndp перед клеткой и не забудь, что финальный валидный профиль — ровно 0 (граница «ровная», ничего не торчит за пределы). Для счёта по модулю меняешь += на сложение по модулю.