Liczba kombinacji dla klocków domino 4xN
Chcę znaleźć liczbę możliwych różnych kombinacji dla obszaru 4 x N (szerokość 4 jednostek i wysokość N jednostek, N ≥ 1) cegieł dominaprzy użyciu programowania dynamicznego .
Cegły Domino mają rozmiar 2x1, np.
==
dla poziomego i
|
|
dla pionowej cegły.
Teraz,
Przykład 4x1 (dwie cegły domina pod sobą)
====
Przykłady konfiguracji cegieł 4x2 (łącznie 5)
1)
||||
||||
2) (Obróć dwie cegły po prawej)
||==
||==
3)
|==|
|==|
4)
====
====
5)
==||
==||
Liczba znanych dotychczas unikalnych kombinacji
4x1 : 1 possibility
4x2 : 5 possibilites
4x3 : 11 possibilites
4x4 : 36 possibilites