Informatică Algoritmi
Ce este programarea dinamica exemple?
Programarea dinamică este o tehnică de proiectare a algoritmilor care rezolvă probleme complexe prin descompunerea lor în subprobleme mai mici și stocarea rezultatelor pentru a evita recalcularea.
Principii de bază
- Subprobleme suprapuse Problema se descompune în subprobleme care se rezolvă de mai multe ori; programarea dinamică memorează soluțiile într-un tabel.
- Stocarea rezultatelor Folosește memoizare (stocare top-down) sau tabulare (stocare bottom-up) pentru a salva rezultatele subproblemelor.
- Optimizare Scopul este să găsească soluția optimă, de obicei minimizând sau maximizând o valoare.
Exemple de probleme
- Șirul lui Fibonacci F(n) = F(n-1) + F(n-2); fără programare dinamică, calculul este exponențial; cu ea, timpul devine liniar stocând valorile într-un vector.
- Problema rucsacului Maximizează valoarea obiectelor într-un rucsac cu capacitate limitată; se folosește o matrice pentru a stoca soluțiile subproblemelor.
- Cea mai lungă subsecvență comună Găsește cea mai lungă secvență comună a două șiruri; se construiește o tabelă 2D cu lungimile subsecvențelor.
Aplică programarea dinamică la probleme de optimizare cu subprobleme repetitive, ca în planificarea resurselor.