Изменения

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