ДП по профилю
Содержание
Задача
Нам дана обычная фигурка для домино($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[mask1][mask2] - можно ли в mask1 поставить доминошки так, чтобы получить в следующем столбике mask2
Тогда теперь у нас будет 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)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль
Изломанный профиль
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin