27
правок
Изменения
Нет описания правки
== Общие принципы ==
Обычно нам дана таблица и надо посчитать количество замещений этой таблицы по некоторому свойству. Можно перебрать все варианты и выбрать из них хорошие. Но можно воспользоваться методом динамическое программирование по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо замостить и для него нам надо k предыдущих линий. Тогда можно перебрать все замещения длиной <tex>k\times n</tex>. В итоге нужно заполнить данную таблицу этими замещениями. Получается, что если перебирать все варианты на понадобиться <tex>O(a^{nm})</tex> времени, а если перебирать только состояния и переходить по ним нам потребуется <tex>O(a^{kn}*m)</tex> времени (где а - количество способов замещения 1 клетки).
== '''Задача о замощении домино''' ==
Найти количество способов замостить таблицу <tex>n\times m</tex> с помощью доминошками размерами <tex>1\times 2,2\times 1</tex>.
==='''Решение:'''===
Для удобства можно хранить профили в виде двоичных масок.
В качестве состояния динамики будем использовать профили размерами n. В этом профиле 1 будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе 0. Таких профилей будет <tex>2^n</tex>.
Ответом будет <tex> \sum a[m][i]</tex>, где i : профиль, который может быть последним (т.е. все группы из 0 имеют четные размеры)
==='''Реализация'''===
//n, m размеры таблицы
[[Файл:Симпатичне узоры.png|240px|thumb|right|]]
==='''Решение:'''===
Для удобства можно хранить профиля в виде двоичных масок
В качестве состояния динамики будем использовать профили размера n. В этом профиле 1 будет означать что клетка закрашена в черный цвет, и 0 если в белый.
Ответом будет <tex> \displaystyle \sum_{j=0}^{2^n -1} a[m][i]</tex>
==='''Реализация:'''===
//n, m размеры таблицы
for i = 0..(1<<n) - 1
