Informatică Algoritmi
Programare dinamica explicata
Programarea dinamică este o metodă de rezolvare a problemelor complexe prin descompunerea lor în subprobleme mai mici și stocarea rezultatelor pentru a evita recalcularea. Este eficientă pentru probleme cu substructură optimală și subprobleme suprapuse, cum ar fi șirul lui Fibonacci sau problema rucsacului. Se bazează pe memoizare sau tabulare.
Pașii de aplicare
- 1 Pasul 1 Identifică subproblemele și relația de recurență între ele.
- 2 Pasul 2 Definește o structură de date (de exemplu, un vector) pentru a stoca rezultatele subproblemelor.
- 3 Pasul 3 Calculează rezultatele de la subproblemele cele mai mici până la cea mare (tabulare) sau folosește memoizare.
- 4 Pasul 4 Construiește soluția finală din rezultatele stocate.
Exemplu: șirul lui Fibonacci cu programare dinamică
- Definiție F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) pentru n ≥ 2.
- Rezolvare naivă Calculează recursiv, dar recalculează aceleași valori de multe ori, complexitate O(2^n).
- Programare dinamică cu tabulare Creezi un vector fib[0..n]; fib[0]=0, fib[1]=1; pentru i de la 2 la n: fib[i] = fib[i-1] + fib[i-2]; complexitate O(n).
- Exemplu numeric pentru n=5 fib[0]=0, fib[1]=1, fib[2]=1, fib[3]=2, fib[4]=3, fib[5]=5 → F(5)=5.
Aplică programarea dinamică când problema are subprobleme care se repetă; începe cu cazurile de bază și construiește progresiv.