Programare dinamica (subsir crescator maxim, rucsac, distanta editare)

Programarea dinamica este o tehnica de rezolvare a problemelor prin descompunerea acestora in subprobleme mai mici, care se suprapun, si prin stocarea rezultatelor intermediare pentru a evita recalcularea. Esecul principal este principiul optimalitatii: o solutie optima pentru problema principala contine solutii optime pentru subproblemele sale.

1. Subsir crescator maxim (LIS): Se da un sir de numere. Se cere cel mai lung subsir (nu neaparat continuu) in care elementele sunt in ordine strict crescatoare. Rezolvarea clasica foloseste o tabela dp[i] = lungimea celui mai lung subsir care se termina la pozitia i. Pentru fiecare i, se cauta un j < i cu a[j] < a[i] si se actualizeaza dp[i] = max(dp[i], dp[j] + 1). Complexitate O(n^2). Exista si varianta optimizata cu cautare binara (O(n log n)) folosind o lista care mentine cele mai mici capete posibile pentru subsiruri de lungime k.

1. Problema rucsacului (Knapsack 0/1): Se dau n obiecte, fiecare cu greutate w[i] si valoare v[i], si un rucsac de capacitate C. Se cere valoarea maxima care poate fi incarcata, fara a depasi capacitatea. Se defineste dp[i][j] = valoarea maxima obtinuta folosind primele i obiecte si o capacitate j. Relatia de recurenta: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) daca j >= w[i], altfel dp[i][j] = dp[i-1][j]. Complexitate O(n*C). Se poate optimiza memoria la un vector unidimensional, iterand capacitatea descrescator.

1. Distanta de editare (Levenshtein): Se dau doua siruri de caractere. Se cere numarul minim de operatii (inserare, stergere, inlocuire) pentru a transforma un sir in celalalt. Se defineste dp[i][j] = distanta minima intre primele i caractere din primul sir si primele j caractere din al doilea sir. Recurenta: daca s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1]; altfel, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Se initializeaza dp[0][j] = j, dp[i][0] = i. Complexitate O(n*m).

Aceste trei probleme sunt clasice in programarea dinamica si apar frecvent in Bacalaureat si in competitii. Intelegerea lor dezvolta gandirea algoritmica si capacitatea de a recunoaste structuri de subprobleme suprapuse.

Exemple

• Exemplul 1: Subsir crescator maxim. Sir: [10, 9, 2, 5, 3, 7, 101, 18]. Se calculeaza dp: pentru 10 -> 1, 9 -> 1, 2 -> 1, 5 -> max(1, dp[2]+1=2) -> 2, 3 -> max(1, dp[2]+1=2) -> 2, 7 -> max(1, dp[2]+1=2, dp[4]+1=3) -> 3, 101 -> max(1, dp[5]+1=4) -> 4, 18 -> max(1, dp[5]+1=4) -> 4. Rezultat: lungimea maxima = 4 (subsirul 2,5,7,101 sau 2,3,7,101). Se demonstreaza pas cu pas.
• Exemplul 2: Rucsac 0/1. Obiecte: (greutate, valoare) = [(2,3), (3,4), (4,5), (5,6)], capacitate C=8. Se construieste tabela dp[5][9]. Initial dp[0][*]=0. Pentru obiectul 1 (g=2, v=3): dp[1][0]=0, dp[1][1]=0, dp[1][2]=3, dp[1][3]=3, ... pana la dp[1][8]=3. Pentru obiectul 2 (g=3, v=4): dp[2][2]=max(3,0)=3, dp[2][3]=max(3,4)=4, dp[2][4]=max(3,4)=4, dp[2][5]=max(3,3+4=7)=7, etc. In final dp[4][8]=10 (obiectele 2,3,4: 3+4+5=12? Nu, greutati: 3+4+5=12>8; solutia corecta: obiectele 1,2,3: 2+3+4=9>8; de fapt, combinatia 1,2,4: 2+3+5=10, greutate 10>8; combinatia 1,3,4: 2+4+5=11>8; combinatia 2,3,4: 3+4+5=12>8; cea mai buna este (1,2) cu valoare 7? Verific: obiectele 1 si 2: g=5, v=7; obiectele 1 si 3: g=6, v=8; obiectele 2 si 3: g=7, v=9; obiectele 1,2,3: g=9>8; obiectele 1,4: g=7, v=9; obiectele 2,4: g=8, v=10; obiectele 3,4: g=9>8. Deci valoarea maxima este 10 (obiectele 2 si 4). Se explica cum se construieste tabela si backtracking.
• Exemplul 3: Distanta de editare. Sir1 = 'abc', Sir2 = 'yabd'. Se initializeaza dp[0][0]=0, dp[0][j]=j, dp[i][0]=i. Se parcurge: i=1, j=1: 'a' vs 'y' -> diferit: dp[1][1]=1+min(dp[0][1]=1, dp[1][0]=1, dp[0][0]=0) = 1+0=1. i=1,j=2: 'a' vs 'ya'? De fapt, dp[1][2] = 1+min(dp[0][2]=2, dp[1][1]=1, dp[0][1]=1) = 1+1=2. etc. Rezultat final dp[3][4]=2 (operatii: inlocuire 'a' cu 'y', inserare 'd' sau stergere 'c' si inserare 'd' etc). Se explica recurenta.

Concepte cheie: Principiul optimalitatii si subprobleme suprapuse, Subsir crescator maxim (LIS) - recurenta clasica si optimizare cu cautare binara, Rucsac 0/1 - tabela bidimensionala si optimizare vectoriala, Distanta de editare (Levenshtein) - operatii: inserare, stergere, inlocuire, Backtracking pentru reconstruirea solutiei (subsir, obiecte selectate)