Я хочу найти количество возможных различных комбинаций для области размером 4 x N (4 единицы ширины и N единиц высоты, N & # x2265; 1) кирпичей доминоusing dynamic programming .

Кирпичи домино имеют размер 2х1, например.

==

для горизонтального и

|
|

для вертикального кирпича.

Сейчас,

Пример 4x1 (два кирпича домино под друг другом)

====

Примеры конфигурации кирпича 4х2 (всего 5)

1)

||||
||||

2) (поверните два кирпича справа)

||==
||==

3)

|==|
|==|

4)

====
====

5)

==||
==|| 

Количество уникальных комбинаций, известных к настоящему времени

4x1 : 1 possibility
4x2 : 5 possibilites
4x3 : 11 possibilites
4x4 : 36 possibilites