p=. !probleme-de-acoperire2?P231.jpg!

* Dacă procedura aşezăm trei dominouri pe linia $4$ şi linia $5$ aşa cum vedem mai sus, atunci vom trece în starea $(5, 011000)$. La final, vom returna valoarea aflată în $numWays[N + 1][0]$ <tex> !! </tex>. Complexitatea ca timp a acestei rezolvări este $O(M * 4^N^)$, iar ca spaţiu este $O(2^N^)$.
 
h2. Problema 4 (Hardwood Floor, acm.sgu.ru)
 
bq. Determinaţi numărul de acoperiri ale unei table de dimensiuni $N x M (1<= N <= 9, 1 <= M <= 9)$ cu piese de tipul:
 
p=. !probleme-de-acoperire?P241.jpg!
 
h3. Soluţie:
 
* Exemplu: Pentru $N = 3$ şi $M = 2$ avem $5$ acoperiri posibile.
* În rezolvare putem folosi direct ideea de rezolvare a problemei anterioare.

* Dacă procedura aşezăm trei dominouri pe linia $4$ şi linia $5$ aşa cum vedem mai sus, atunci vom trece în starea $(5, 011000)$. La final, vom returna valoarea aflată în $numWays[N + 1][0]$ <tex> !! </tex>. Complexitatea ca timp a acestei rezolvări este $O(M * 4^N^)$, iar ca spaţiu este $O(2^N^)$.