PROGRAMARE DINAMICĂ
Programarea dinamică rezolvă problemele prin descompunerea lor în subprobleme şi prin combinarea rezolvărilor acestora (termenul „programare" se referă aici la o metodă tabulară). Spre deosebire de divide et impera, care considera că subproblemele sunt independente, programarea dinamică se aplică atunci când subproblemele nu sunt independente. Într-un astfel de caz, divide et impera ar efectua calcule redundante, rezolvând fiecare subproblemă ca şi când nu ar mai fi întâlnit-o. Programarea dinamică, însă, salvează rezultatul fiecărei subprobleme într-o tabelă, evitând astfel rezolvarea redundantă a aceleiaşi probleme.
Programarea dinamică se aplică în general problemelor de optimizare, atunci când dorim să determinăm rapid soluţia optimă pentru o problemă. De fapt, aplicând această tehnică determinăm una din soluţiile optime, problema putând avea mai multe soluţii optime.
Aplicarea acestei tehnici de programare poate fi descompusă în următoarea secvenţă de paşi:
1. Descoperirea structurii şi "măsurii" pe care o are o soluţie optimă.
2. Definirea recursivă a valorii care caracterizează o soluţie optimă.
3. Calcularea "de jos în sus" a acestei valori.
4. Construirea soluţiei optime pornind de la calculele efectuate anterior.
Fie problelma găsirii unui şir comun în două şiruri date. Modul de abordare a acestei probleme prin metoda programării dinamice poate fi urmărit în clipul de mai jos:
De exemplu, pentru valorile de mai jos:
6
a c b a e d
7
a b c a d f d
se obţin rezultatele:
CEVA