Programare dinamica (subsir comun maximal, rucsac, problema schimbului)

Programarea dinamica este o paradigma de programare utilizata pentru rezolvarea problemelor care prezinta proprietatea de substructura optima si suprapunere a subproblemelor. In loc sa rezolvam problema direct prin recursivitate pura, care duce la complexitate exponentiala, programarea dinamica descompune problema in subprobleme mai mici, rezolva fiecare subproblema o singura data, stocheaza rezultatele intr-o tabela (de obicei un array sau matrice) si le reutilizeaza pentru a construi solutia optima globala. Cele trei probleme clasice studiate la bacalaureat sunt:

1. Subsirul comun maximal (LCS): Se dau doua siruri de caractere (sau numere) si se cere lungimea celui mai lung subsir care apare in ambele siruri, pastrand ordinea caracterelor. Substructura optima: daca ultimele caractere coincid, le includem in solutie si continuam cu restul sirurilor; altfel, alegem maximul dintre solutia obtinuta prin eliminarea unui caracter din primul sir si cea prin eliminarea unui caracter din al doilea sir. Se utilizeaza o matrice de dimensiune (n+1) x (m+1) unde dp[i][j] = LCS pentru prefixele de lungime i si j.

1. Problema rucsacului (Knapsack): Avem un set de obiecte, fiecare cu o greutate si o valoare, si un rucsac de capacitate C. Se cere valoarea maxima care poate fi incarcata. Varianta clasica este rucsacul 0/1 (fiecare obiect se ia sau nu). Substructura optima: pentru fiecare obiect, decizia se bazeaza pe compararea valorii obtinute daca il includem (adunand valoarea lui si rezolvand subproblema cu capacitatea redusa) cu valoarea daca nu il includem. Se construieste o matrice dp[i][j] = valoarea maxima folosind primele i obiecte si capacitatea j.

1. Problema schimbului (Coin Change): Se da o suma S si un set de monede cu valori date (numar nelimitat de monede). Se cere numarul minim de monede pentru a forma suma S (sau numarul de modalitati). Substructura optima: pentru fiecare suma, incercam toate monedele si alegem minimul dintre (1 + solutia pentru suma curenta minus valoarea monedei). Se foloseste un array dp[S+1] unde dp[s] = numarul minim de monede pentru suma s.

Toate aceste probleme se rezolva prin construirea solutiei de jos in sus (bottom-up) sau prin memoizare (top-down). Complexitatea tipica este O(n*m) pentru LCS, O(n*C) pentru rucsac si O(n*S) pentru schimb. La bacalaureat, se cer explicatii ale recurentei, initializarea tabelei si reconstructia solutiei.

Exemple

• Exemplul 1: Subsir comun maximal (LCS) - Sir1: 'abcde', Sir2: 'ace'. Se construieste matricea 6x4. Rezultat: lungimea = 3 (subsirul 'ace'). Detalii: dp[1][1]=1 pentru 'a' cu 'a', dp[2][2]=2 pentru 'ab' cu 'ac'? Nu, de fapt la final dp[5][3]=3. Explicatie pas cu pas: initializare linia 0 si coloana 0 cu 0. Pentru i=1..5, j=1..3, daca sir1[i-1]==sir2[j-1] atunci dp[i][j]=dp[i-1][j-1]+1, altfel dp[i][j]=max(dp[i-1][j], dp[i][j-1]). Rezultatul este dp[5][3].
• Exemplul 2: Rucsac 0/1 - Capacitate C=5, obiecte: (greutate, valoare): (2,3), (3,4), (4,5). Se construieste matrice 4x6. Initializare cu 0. Pentru fiecare obiect, pentru fiecare capacitate, se decide: daca greutatea <= capacitate, dp[i][j]=max(dp[i-1][j], dp[i-1][j-greutate]+valoare); altfel dp[i][j]=dp[i-1][j]. Rezultat optim: 7 (obiectele 1 si 2).
• Exemplul 3: Problema schimbului - Suma S=11, monede: [1,2,5]. Se construieste array dp[0..11] initializat cu INF, dp[0]=0. Pentru fiecare suma s de la 1 la 11, pentru fiecare moneda m, daca s>=m, dp[s]=min(dp[s], dp[s-m]+1). Rezultat: dp[11]=3 (5+5+1).

Concepte cheie: Substructura optima: solutia optima a problemei poate fi construita din solutii optime ale subproblemelor., Suprapunerea subproblemelor: aceleasi subprobleme sunt rezolvate de mai multe ori, deci prin memorare evitam recalcularea., Tabela de programare dinamica: structura de date (matrice sau vector) care stocheaza rezultatele subproblemelor pentru a fi reutilizate.