Eu quero encontrar o número de possíveis combinações diferentes para uma área de 4 x N (4 unidades de largura e N unidades de altura, N ≥ 1) de tijolos de dominóusando programação dinâmica .

Os tijolos de dominó têm um tamanho de 2x1, e.

==

para uma horizontal e

|
|

para um tijolo vertical.

Agora,

Exemplo 4x1 (dois tijolos de dominó abaixo um do outro)

====

Exemplos para configurações de tijolos de 4x2 (5 no total)

1)

||||
||||

2) (vire dois tijolos à direita)

||==
||==

3)

|==|
|==|

4)

====
====

5)

==||
==|| 

Número de combinações exclusivas conhecidas até agora

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