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