Informatică Algoritmi
Programare dinamica exercitii bacalaureat
Programarea dinamică la bacalaureat rezolvă probleme prin descompunerea lor în subprobleme mai mici și stocarea rezultatelor pentru a evita recalcularea. Ea este folosită pentru optimizare, cum ar fi în problema rucsacului sau a șirului Fibonacci. De exemplu, pentru Fibonacci, se poate calcula F(n) = F(n-1) + F(n-2) folosind un vector pentru a memora valorile anterioare.
Exerciții tipice de programare dinamică
- Șirul Fibonacci Calculează F(n) folosind un vector dp unde dp[i] = dp[i-1] + dp[i-2], cu dp[0]=0, dp[1]=1, complexitate O(n).
- Problema rucsacului 0/1 Maximizează valoarea obiectelor într-un rucsac cu capacitate dată, folosind o matrice dp[i][w] pentru obiecte i și greutate w.
- Drumul minim într-o matrice Găsește suma minimă de la colțul stânga-sus la dreapta-jos într-o matrice, cu dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrice[i][j].
Pași pentru rezolvare
- 1 Identifică subproblemele Stabilește cum se descompune problema, de exemplu în Fibonacci, fiecare termen depinde de cei anteriori.
- 2 Definește relația de recurență Scrie formula matematică, cum ar fi dp[n] = dp[n-1] + dp[n-2] pentru Fibonacci.
- 3 Implementează cu memorare Folosește un vector sau matrice pentru a stoca rezultatele și calculează de la cazurile de bază în sus.
Începe cu exerciții simple și verifică recurența înainte de a scrie cod.