h3. Soluţie:
* 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$.

* 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ă.
h2. Problema 7 (Bugs, CEOI 2002, [2])