Изменения

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

'''println'''<tex>((\mathtt{p} - (\mathtt{2} \verb|<<| \ \mathtt{i})) \verb|<<| \ \mathtt{1}</tex>, " ", <tex>\mathtt{0})</tex>

'''println'''<tex>(\mathtt{p} - (\mathtt{2} \verb|<<| \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex>

'''println'''<tex>((\mathtt{p} \verb|<<| \ \mathtt{1})</tex>, " ", <tex>\mathtt{0})</tex>

'''println'''<tex>(\mathtt{p} + (\mathtt{1} \verb|<<| \ \mathtt{n})</tex>, " ", <tex>(\mathtt{i} + \mathtt{1}) % \mathtt{n})</tex>

'''println'''<tex>(\mathtt{p} + (\mathtt{4} \verb|<<| \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex>