ДП по профилю

Задача

Нам дана обычная фигурка для домино($1 \times 2$), мы можем ее класть на поле в виде $1 \times 2$ или $2 \times 1$. Требуется сказать количество способов замостить доску доминошками

Наивное решение

Давайте запустим перебор рекурсией и честно посчитаем количество способов. Это работает за очень долго. Подумаем, как это оптимизировать.

Динамика

Заметим, что столбик однозначно определяется двоичной маской(0 - свободно, 1 - покрывается какой-то доминошкой), но мы уже научились делать динамику по подмаскам, давайте применим здесь ту же идею.

Широкий профиль

Пусть dp[i][j][mask1][mask2] - количество способов замостить доску до $i$-го столбика, притом чтобы $i$-й столбик кодировался маской mask1, а $i + 1$-й - $mask2$, и мы сейчас рассматривали $j$-ую позицию в $i$-м столбике

1) База динамики - dp[0][0][0][0] = 1

2) Ответ - dp[n - 1][j][(1 << m) - 1][0]

3) Переходы :

Будем перебирать позицию в маске mask1

1 for (int j = 0; j < m; j++) {
2     if ((1 << j) & mask1) { //j-й бит уже занят и поэтому мы не можем поставить доминошки
3         continue;
4     }
5     dp[i][j + 1][mask1 | (1 << j)][mask2 | (1 << j)] += dp[i][j][mask1][mask2]; //горизонтальная, рассмотреть случай, если мы на границе столбика
6     if ((1 << (j + 1)) & mask1) { //(j + 1)-й бит свободен, надо проверить еще, что он существует
7         dp[i][j + 2][mask1 | (1 << j) | (1 << (j + 1))][mask2] += dp[i][j][mask1][mask2];//также рассмотреть границу отдельно
8     }
9 }

В данной идее много граничных случаев, поэтому сейчас мы рассмотрим два других решения этой задачи

Обычный профиль

Пусть $can[mask_{1}][mask_{2}]$ - можно ли в $mask_{1}$ поставить доминошки так, чтобы получить в следующем столбике $mask_{2}$

Тогда теперь у нас будет $dp[i][mask]$ - мы рассматриваем $i$-ый столбик и хотим в нем собрать mask, сколько способов существует

теперь у нас будут очень простые переходы :

1 for (int mask1 = 0; mask1 < (1 << m); mask1++) {
2      dp[i + 1][mask1] += dp[i][mask] * can[mask][mask1];
3 }

Оценка асимпотики

К сожалению оба способа работают достаточно долго, а именно Широкий профиль за $O(n \cdot m \cdot 2^m \cdot 2^m)$, так как мы перебираем столбик, строку, первую и вторую маску, Обычный же за $O(n \cdot 2^m \cdot 2^m)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль

Изломанный профиль

Уже в названии подхода содержится его идея - давайте сломаем нашу маску, пускай теперь маска означает не весь $i$-й столбик, а ячейки с $j$-ячейки $i$-ого столбика до $m - 1$-й ячейки $i$-ого столбика и ячейки с $0$-ячейки $i + 1$-ого столбика до $j + 1$-й ячейки $i + 1$-ого столбика

https://wampi.ru/image/6p95C8Q

Тогда теперь у нас есть $dp[i][j][mask]$ - сколько способов дойти до $j$ ячейки $i$ строки с маской $mask$ у нас есть

1) База $dp[0][0][0] = 1$

2) Ответ - в зависимости от реализации, но я обычно пишу так, чтобы ответ лежал в $dp[n][0][0]$ - нулевая строка столбика, которого нет в таблице и маска равна 0

3) Переходы - Практически все остается как в широком профиле, единственное нам теперь нужно сдвигать маску вниз, но для этого в плюсах есть операция >>

Оценка асимпотики

$n \cdot m \cdot 2^m$

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin