Изменения

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

  <font color=green>// n, m размеры - размер таблицы </font> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''for ''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''if ''' можно перейти из <tex>i </tex> в <tex>j </tex> профиль <tex>\mathtt{d}[i][j] = \mathtt{1; }</tex> '''else ''' <tex>\mathtt{d}[i][j] = \mathtt{0;}</tex> <tex>\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1; }</tex> <font color=green>// Так как мы можем начать только с профиля где все клетки 0</font> '''for ''' <tex>k = \mathtt{1}..m - \mathtt{1} </tex> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''for ''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> <tex>\mathtt{a}[k][i] = \mathtt{a}[k][i] += \mathtt{a}[k-\mathtt{1}][j] * \cdot \mathtt{d}[j][i];</tex> <tex>ans = \mathtt{0;}</tex> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''if ''' можно закончить <tex>i </tex> профилем <tex>ans = ans += \mathtt{a}[m-\mathtt{1}][i];</tex> '''return ''' <tex>ans;</tex>

<font color=green>// n, m размеры - размер таблицы </font> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''for ''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''if ''' можно перейти из <tex>i </tex> в <tex>j </tex> профиль <tex>\mathtt{d}[i][j] \ = \ \mathtt{1; }</tex> '''else ''' <tex>\mathtt{d}[i][j] \ = \ \mathtt{0;}</tex> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> <tex>\mathtt{a}[i][0] \ = \mathtt{1; }</tex> <font color=green >// Так как мы можем начать c любого профиля</font> '''for ''' <tex>k = \mathtt{1}..m - \mathtt{1} </tex> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> '''for ''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> <tex>\mathtt{a}[k][i] = \mathtt{a}[k][i] += \mathtt{a}[k-1][j] * \cdot \mathtt{d}[j][i];</tex> <tex>ans = \mathtt{0;}</tex> '''for ''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> <tex>ans = ans += a[m-\mathtt{1}][i] </tex> <font color=green>// Так как мы можем закончить любым профилем</font> '''return ''' <tex>ans;</tex>