* Din nou vom folosi $metoda programării dinamice$ îmbinată cu metoda $backtraking$.
* Vom umple tabla linie cu linie şi la fiecare pas putem pune dominouri orizontale pe linia curentă şi verticale pe linia curentă şi linia următoare. Trebuie să fim atenţi când trecem de la linia curentă la următoarea să nu lăsăm pe linia curentă loc liber unde poate fi amplasat un domino orizontal, pentru că acest loc nu va putea fi ocupat de piese amplasate mai târziu. Se poate lăsa spaţiu gol pe linia curentă şi linia următoare pentru că o celulă a acestei poziţii va putea fi acoperită la pasul următor. Vedem astfel că dacă linia curentă este linia $i$ atunci avem trei stări posibile pentru ultimele două pătrăţele de pe fiecare coloană: $00$ (celule neocupate),  $10$ (penultima celulă ocupată şi ultima goală) $11$ (ambele celule ocupate de dominouri), starea $01$ nu poate exista. În procedura $backtracking$ care generează configuraţiile la care putem ajunge de la o configuraţie dată trebuie să mai avem grijă să nu ocupăm cu un domino o celulă ce nu aparţine tablei. Astfel, pentru a găsi soluţia problemei vom folosi un tablou $min[i][config]$ care va păstra numărul minim de dominouri care trebuie amplasate pe tablă astfel ca pe liniile $1 .. i – 1$ să nu poată fi amplasat vreun domino pe celulele rămase goale, $config$ va fi un număr întreg care atunci cănd e transformat în baza $3$ arată configuraţia liniilor $i – 1$ şi $i$.

* La fiecare pas, procedura $backtracking$ alege dacă să pună un domino orizontal, unul vertical sau să treacă mai departe, deci o limită superioară ar fi $O(3^M^)$ operaţii (nu toate configuraţiile vor fi posibile). În tablou avem $N x 3^M^$ stări, deci complexitatea algoritmului este $O(N * 9^M^)$. Menţionăm din nou că aceasta este o limită superioară şi că algoritmul se va comporta mult mai bine în practică.

* La fiecare pas, procedura $backtracking$ alege dacă să pună un domino orizontal, unul vertical sau să treacă mai departe, deci o limită superioară ar fi $O(3^M^)$ operaţii (nu toate configuraţiile vor fi posibile). În tablou avem $N x 3^M^$ stări, deci complexitatea algoritmului este $O(N * 9^M^)$. Menţionăm din nou că aceasta este o limită superioară şi că algoritmul se va comporta mult mai bine în practică.
 
h2. Problema 7 (Bugs, CEOI 2002, [2])
 
bq. Să se acopere o tablă de dimensiuni $M x N (1 <= M <= 10, 1 <= N <= 150)$ cu un număr maxim de piese de dimensiuni $3 x 2$ şi $2 x 3$. Tabla are unele celule ce trebuie să nu fie acoperite, iar oricare două piese nu se pot suprapune. Pentru tabla de mai jos, numărul maxim de piese cu care se poate acoperi este $3$.
 
p=. !probleme-de-acoperire2?P272.jpg!
 
h3. Soluţie:
 
* Evident, putem încerca o soluţie identică cu cea a $Problemei 1$, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.
* Există o rezolvare de complexitate $O(N * M * 3^M^)$ care aşa cum deja v-aţi obişnuit combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va avea iniţial $max[i][j][config]$ egal cu $0$. Iterăm rândurile în ordinea $1 .. N$ ,coloanele în ordinea $1 .. M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul de stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i <= i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $004 este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $24 (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):
 
p=. !probleme-de-acoperire2?P273.jpg!
 
* Dacă decidem să nu punem piesă în pătrăţelul $(4, 3)$ atunci din starea $(4, 3, 1000212)$ trecem în starea $(5, 3, 10000212)$.
 
p=. !probleme-de-acoperire2?P274.jpg!
 
* Dacă punem o piesă verticală ajungem în starea $(7, 3, 1111212)$.
 
p=. !probleme-de-acoperire2?P275.jpg!
 
* Iar dacă punem o piesă orizontală atunci ajungem în starea $(6, 3, 1022212)$.
 
p=. !probleme-de-acoperire2?P276.jpg!
 
* Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][&#48;]$. Menţionăm că $Problemele 2, 3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.