Informatică Algoritmi
Programare dinamica probleme rezolvate
Programarea dinamică rezolvă probleme complexe prin descompunerea în subprobleme mai mici, stocând rezultatele pentru a evita recalculările. O problemă tipică este șirul lui Fibonacci, unde F(n) = F(n-1) + F(n-2), cu F(0)=0, F(1)=1. Fără memoizare, complexitatea este exponențială, dar cu programare dinamică devine O(n).
Probleme rezolvate cu pași
- 1 Problema rucsacului 0-1 Se dă un rucsac cu capacitate W și n obiecte cu greutăți g[i] și valori v[i]. Se calculează dp[i][w] = valoarea maximă folosind primele i obiecte și greutatea w. Formula: dp[i][w] = max(dp[i-1][w], dp[i-1][w-g[i]] + v[i]) dacă g[i] <= w, altfel dp[i-1][w].
- 2 Șirul crescător maximal Pentru un vector a de lungime n, se găsește lungimea celui mai lung subșir crescător. Se folosește dp[i] = lungimea maximă care se termină la poziția i, calculată ca 1 + max(dp[j]) pentru j < i cu a[j] < a[i].
- 3 Problema schimbului de monede Se dă o sumă S și monede cu valori c[1..m]. Se calculează dp[s] = numărul minim de monede pentru suma s. Formula: dp[s] = min(dp[s-c[i]] + 1) pentru toate i cu c[i] <= s.
Exemple numerice
- Fibonacci cu memoizare Pentru n=5: F(0)=0, F(1)=1, F(2)=F(1)+F(0)=1, F(3)=F(2)+F(1)=2, F(4)=F(3)+F(2)=3, F(5)=F(4)+F(3)=5. Se stochează valorile într-un vector.
- Rucsac 0-1 exemplu W=5, obiecte: (greutate=2, valoare=3), (3,4), (4,5). dp[2][5] = max(dp[1][5], dp[1][2]+4) = max(3, 3+4)=7.
Începe cu cazurile de bază și construiește tabelul dp de jos în sus pentru eficiență.