Изменения

Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо <tex>k </tex> предыдущих линий. Тогда можно перебрать все замощения длиной <tex>k\times n</tex>. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобиться <tex>O(a^{nm})</tex> времени, а если перебирать только состояния и переходить по ним нам потребуется <tex>O(a^{kn}*m)</tex> времени (где а - количество способов замещения 1 клетки).

В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле 1 будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе 0. Таких профилей будет <tex>2^n</tex>.

[[Файл:Домино.png|270px|thumb|right|Переходы(1-правильный переход, 2,3-неправильные)]]

Из профиля <tex>i </tex> в профиль <tex>j </tex> можно перейти если выполняются условия:

* Можно положить горизонтальные домино. То есть там где в <tex>j </tex> профиле стоит 1, в <tex>i </tex> профиле должен стоять 0

* Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся 0 в <tex>i </tex> профиле должны образовывать четные подстроки.

Пусть <tex>d[i][j] = 1</tex> если из профиля <tex>i </tex> можно перейти в <tex>j</tex>-ый, иначе 0.

Пусть так же <tex>a[k][i]</tex> - количество способов замощения первых <tex>k-1 </tex> столбцов и заканчивавшийся на <tex>i</tex>-ом профиле.

Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i </tex> : профиль, который может быть последним (т.е. все группы из 0 имеют четные размеры)

<tex>O(2^{2n}+2^{2n}\times m)</tex>, так же можно заметить что в массиве <tex>a</tex> для <tex>k </tex> состояния нам нужно только <tex>k-1 </tex> состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив <tex>d</tex>, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2\times 2^n)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из <tex>i </tex> в <tex>j </tex> равно <tex>n </tex> и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>.

В качестве состояния динамики будем использовать профили размера <tex>n</tex>. В этом профиле 1 будет означать что клетка закрашена в черный цвет, и 0 если в белый.Из профиля <tex>i </tex> в <tex>j</tex>-ый можно перейти если выполнено условие:* если поставить <tex>i </tex> и <tex>j </tex> профиль рядом, то не должно быть квадратов <tex>2\times 2</tex> одного цвета

Пусть <tex>d[i][j] = 1</tex> если из профиля <tex>i </tex> можно перейти в <tex>j</tex>-ый, иначе 0.

Пусть так же <tex>a[k][i]</tex> - количество способов раскрашивания первые <tex>k-1 </tex> столбцов и заканчивавшийся на <tex>i</tex>-ом профиле.

<tex>O(2^{2n}+2^{2n}\times m)</tex>, так же можно заметить что в массиве <tex>a</tex> для <tex>k </tex> состояния нам нужно только <tex>k-1 </tex> состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив <tex>d</tex>, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2\times 2^n)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из <tex>i </tex> в <tex>j </tex> равно <tex>n </tex> и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>.