27
правок
Изменения
Нет описания правки
}}
{{Определение
|definition='''Профиль''' - один из столбцов(строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.
}}
== Общие принципы ==
Обычно нам дана таблица и надо посчитать количество замощений этой таблицы по некоторому свойствунекоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо 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, m размеры таблицы
for i = 0..(1<<n) - 1
for j = 0..(1<<n) - 1
else
d[i][j] = 0;
a[0][0] = 1; //Так как мы можем начать только с профиля где все клетки 0
for k = 1..m - 1
for i = 0..(1<<n) - 1
return ans;
''' Оценка сложности : '''
подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}\times m</tex> в итоге <tex>O(2^{2n}\times m)</tex>
''' Оценка памяти : '''
<tex>O(2^{2n}+2^{2n}\times m)</tex>, так же можно заметить что в массиве <tex>a</tex> для k состояния нам нужно только k-1 состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2\times 2^n)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из i в j равно n и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>.
== '''Задача о симпатичных узорах''' ==
==='''Условие'''===
Дана таблица <tex>n\times m</tex>, каждая клетка которой может быть окрашена в один из двух
цветов: белый или черный. Симпатичным узором называется такая раскраска, при
==='''Реализация'''===
//n, m размеры таблицы
for i = 0..(1<<n) - 1
for j = 0..(1<<n) - 1
d[i][j] = 0;
for i = 0..(1<<n) - 1
a[i][0] = 1; //Так как мы можем начать c любого профиля
for k = 1..m - 1
for i = 0..(1<<n) - 1
ans = 0;
for i = 0..(1<<n) - 1
ans += a[m-1][i]//Так как мы можем закончить любым профилем
return ans;
''' Оценка сложности : '''
подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}\times m</tex> в итоге <tex>O(2^{2n}\times m)</tex>
''' Оценка памяти : '''
<tex>O(2^{2n}+2^{2n}\times m)</tex>, так же можно заметить что в массиве <tex>a</tex> для k состояния нам нужно только k-1 состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2\times 2^n)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из i в j равно n и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>.
