Informatică Programare
Programare dinamica C++ exemple
Programarea dinamică în C++ rezolvă probleme complexe prin descompunerea în subprobleme mai simple, stocând rezultatele pentru a evita recalcularea. Este folosită pentru optimizare, ca în problema rucsacului sau Fibonacci.
Principii
- Substructură optimă Soluția optimă a problemei se obține din soluțiile optime ale subproblemelor.
- Subprobleme suprapuse Subproblemele se repetă, așa că rezultatele sunt memorate într-un tabel (ex: vector sau matrice).
- Abordări Top-down (cu memoizare) sau bottom-up (iterativ, construind soluția de la subprobleme mici la mari).
Exemplu: Șirul Fibonacci
- 1 Definiție recursivă Fib(n) = Fib(n-1) + Fib(n-2), cu Fib(0)=0, Fib(1)=1. Fără PD, complexitatea este exponențială.
- 2 Soluție bottom-up int fib[100]; fib[0]=0; fib[1]=1; for(int i=2; i<=n; i++) fib[i] = fib[i-1] + fib[i-2];
- 3 Complexitate O(n) cu PD, față de O(2^n) fără, datorită stocării rezultatelor în vectorul fib.
- 4 Exemplu numeric Pentru n=5: fib[2]=1, fib[3]=2, fib[4]=3, fib[5]=5.
Identifică subproblemele suprapuse pentru a aplica programarea dinamică și reduce timpul de execuție.