Изменения

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

Теперь проверим из какого профиля в какой можно перейти.

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

''' Оценка памяти : '''

<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>.

== '''Задача о симпатичных узорах''' ==