Informatică Algoritmi
Dinamica in programare exemple
Programarea dinamică este o tehnică de rezolvare a problemelor prin descompunerea lor în subprobleme mai mici și stocarea rezultatelor. Ea evită recalculările și crește eficiența. În bacalaureat, apare la probleme care cer optimizare, cum ar fi șiruri sau drumuri.
Exemple clasice de probleme
- Șirul lui Fibonacci Calculează termenul n al șirului Fibonacci fără recursivitate ineficientă. Formula: dp[i] = dp[i-1] + dp[i-2], cu dp[0]=0, dp[1]=1. Exemplu: pentru n=5, dp=[0,1,1,2,3,5], rezultat 5.
- Problema rucsacului Maximizează valoarea obiectelor într-un rucsac cu capacitate limitată. Folosești o matrice dp[i][j] pentru valoarea maximă cu primele i obiecte și greutate j. Exemplu: obiecte cu greutate și valoare, calculezi iterativ.
- Drumul minim într-o matrice Găsește suma minimă a unui drum de la colțul stânga-sus la dreapta-jos, mergând doar dreapta sau jos. Formula: dp[i][j] = matrice[i][j] + min(dp[i-1][j], dp[i][j-1]). Exemplu: pentru matrice 2x2, calculezi pas cu pas.
Pași pentru rezolvare
- 1 Identifică subproblemele Stabilește ce rezultate parțiale trebuie calculate și stocate, de obicei într-un vector sau matrice.
- 2 Definește relația de recurență Scrie formula care leagă soluția unei subprobleme de soluțiile subproblemelor mai mici, ca în exemplele de mai sus.
- 3 Stabilește cazurile de bază Determină valorile inițiale pentru cele mai mici subprobleme, cum ar fi dp[0] sau dp[1] în Fibonacci.
- 4 Implementează iterativ Calculează dp de la cazurile de bază până la soluția finală, folosind bucle pentru a evita recursivitatea.
- 5 Extrage rezultatul Accesează dp la poziția corespunzătoare problemei inițiale, de exemplu dp[n] pentru Fibonacci.
Practică probleme simple pentru a înțelege logica recurenței înainte de a trece la cele complexe.