bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 15, M <= 15)$ cu dominouri.

h3. Soluţie:
* Am văzut în numărul anterior că există o formulă pentru acest număr. Abordarea matematică poate fi generalizată şi pentru mai multe probleme asemănătoare de acoperire, dar cunoştinţele necesare sunt avansate, deci această abordare nu ne prea ajută pe noi ca informaticieni.
* O soluţie care ne va da numărul exact şi ar fi putut fi folosită în concurs este asemănătoare celei expuse mai sus. Vom folosi o combinaţie a metodei $backtracking$ cu metoda $programării dinamice$. Tabloul $numWays[i][config]$ va fi numărul de posibilităţi de a acoperi complet primele $i - 1$ coloane ale unei table, iar pe coloana $i$ pătratele ocupate sunt reprezentate de mulţimea $config$. Astfel, $numWays[i + 1][config1]$  va fi egal cu suma de $numWays[i][config]$ unde putem acoperi cu dominouri două coloane astfel ca pe prima coloană să nu fie acoperite celulele date de $config$ şi pe a doua coloană să fie acoperite celulele date de $config1$. De exemplu, starea dată de $(4, 100100)$ este prezentată în următoarea figură:

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^)$.