h2. Programare dinamica folosind bitmask

h2. Programare dinamică folosind măşti de biţi şi codificări binare sau $k$-are

In continuare vom vedea un exemplu de programare dinamica unde vom folosi un bitmask (codificat pe un intreg) pentru a tine spatiul starilor.

Unele probleme de programare dinamica au drept componentă a stării unei subprobleme o mulţime de elemente care fac parte din subproblemă. Astfel, subproblema nu este o reducere a problemei iniţiale la un subset continuu de elemente ($1..i$ sau $i..j$) ci la un subset oarecare. În acest caz, codificăm submulţimea curentă în stare, ca vector sau ca număr întreg. Dacă dimensiunea submulţimii este suficient de mic putem folosi un întreg pentru a codifica această informaţie astfel:

Astfel sa presupunem ca avem nevoie sa tinem un vector caracteristic pentru o multime.
Daca cardinalul acesteia este suficient de mic putem folosi un intreg pentru a codifica aceasta informatie astfel:

Fie mulţimea $A$ = { x{~1~}, x{~2~}, ... x{~n~} }.
Atunci masca de biţi a unei partitii a lui $A, $MASK$, va avea bitul $i$ egal cu 1 dacă şi numai dacă x{~i~} apartine partitiei. Desigur, această reprezentare duce la o complexitate direct proporţională cu $2 ^card(A)^$. Putem intui dacă trebuie să folosim o astfel de rezolvare din limitele valorilor de intrare; pentru $N$ cu valori cuprinse între $10-20$, deducem că trebuie să căutăm o astfel de soluţie.

Fie multimea A = { x{~1~}, x{~2~}, ... x{~n~} }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca x{~i~} apartine partitiei.
 
Desigur, aceasta reprezentare duce la o complexitate direct proportionala cu 2 ^card(A)^.

Pentru multe probleme, fiecare element poate face parte din subproblemă în mai mult de 2 feluri. De exemplu, dacă starea reprezintă o linie de maxim $K$ elemente dintr-o matrice iar fiecare element de pe linie poate avea valorile 0, 1 sau 2 atunci există $3^K$ variante distincte posibile pentru o astfel de linie. Un alt exemplu este o problemă de optimizare în care fiecare element (participant) se poate afla în una din câteva stări (dacă $N$ persoane trebuie să treacă un pod peste un râu, cele 3 stări pot fi: _pe malul stâng_, _pe pod_ şi _pe malul drept_).

h3(#problema-1). Problema 1: 'Be a Smart Raftsman':http://acm.sgu.ru/problem.php?contest=0&problem=475 (SGU)

h2. Programare dinamica pe mai multe dimensiuni

h3(#problema-1). Problema 1: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)
bq. Un număr se numeşte *urât* dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact $2, 3, 5, 7$. Se dă un şir de $N$ cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele $3^N-1^$ variante de a insera semnele generează numere urâte.