Informatică Sisteme de operare
Dynamic programming probleme rezolvate
Programarea dinamică (dynamic programming) este o tehnică de optimizare care rezolvă probleme complexe prin descompunerea în subprobleme mai mici și stocarea rezultatelor. Un exemplu clasic este Șirul lui Fibonacci.
Problema Fibonacci cu memoizare
- 1 Pasul 1: Definirea recurenței F(n) = F(n-1) + F(n-2), cu F(0)=0, F(1)=1. Fără optimizare, complexitatea este exponențială.
- 2 Pasul 2: Crearea unui tablou Declară un vector dp de dimensiune n+1 pentru a stoca valorile calculate, dp[0]=0, dp[1]=1.
- 3 Pasul 3: Calcul iterativ Pentru i de la 2 la n, dp[i] = dp[i-1] + dp[i-2]. Pentru n=5, dp = [0,1,1,2,3,5].
Problema rucsacului (0-1 knapsack)
- 1 Pasul 1: Datele problemei Avem obiecte cu greutăți w = [2,3,4] și valori v = [3,4,5], capacitate maximă C=5.
- 2 Pasul 2: Tabela DP Construiește o matrice dp[i][c] unde i este numărul de obiecte, c este capacitatea. Inițializează cu 0.
- 3 Pasul 3: Calcul Pentru fiecare obiect i, pentru c de la 0 la C: dacă w[i] <= c, dp[i][c] = max(dp[i-1][c], v[i] + dp[i-1][c-w[i]]). Rezultatul maxim este dp[3][5]=7.
Exersează probleme pe platforme ca LeetCode, începând cu "Climbing Stairs" sau "Coin Change" pentru a înțelege pattern-urile.