Ce este programarea dinamică?
În informatică, programarea dinamică este o metodă de elaborare a algoritmilor ce se aplică în general problemelor pentru care se cere determinarea unui optim în urma abordării unor decizii. Nu există un criteriu anume pe baza căruia sa identificăm o problemă pentru rezolvarea căreia trebuie să utilizăm metoda programării dinamice, dar putem formula două proprietăți care sugerează o soluție prin programare dinamică.
​
Substructura optimală
Problema dată poate fi descompusă în subprobleme și soluția optimă a problemei depinde de soluțiile optime ale subproblemelor sale. Acest criteriu nu indică neapărat o soluție bazată pe metoda programării dinamice, ar putea fi un indiciu ca se poate aplica metoda sau metoda .
Subprobleme superpozabile
Subprobleme problemei date nu sunt independente, ci se suprapun. Astfel, în cazul rezolvării unei probleme de programare dinamică, o abordare de tip ar fi dezastroasă din punct de vedere a timpului de execuție deoarece din cauza suprapunerii subproblemelor, un algoritm bazat pe această metodă ar rezolva de mai multe ori aceiași subproblemă. Prin urmare, subproblemele vor fi rezolvate o singură dată, reținând rezultatele intr-o structură de date suplimentară (de obicei un tablou).
Etapele principale în aplicarea metodei
1. Se identifică subproblemele problemei date.
2. Se alege o structură de date capabilă să rețină soluțiile subproblemelor.
3. Se caracterizează substructura optimală a problemei printr-o relație de recurență.
4. Pentru a determina soluția optimă, se rezolvă relația de recurență în mod bottom-up, adică se rezolvă subproblemele în ordine crescătoare a dimensiunilor lor.
Dezvoltarea relațiilor de recurență
Precum în matematică, spunem că un șir ( a n ) n ∈ N {\displaystyle (a_{n})_{n\in \mathbb {N} }}este definit printr-o relație de recurență dacă fiecare termen al acestuia poate fi scris ca o funcție de termenii anteriori. În informatică, există două abordări principale pentru a dezvolta o relație de recurență:
1. Ascendentă (bottom up): se pornește de la cazul particular și se generează noi valori pe baza celor existente.
2. Descendentă (top down): valoarea de calculat se exprimă prin valori anterioare, care trebuie la rândul lor calculate. Această abordare se implementeazăde regulă recursiv (și de cele mai multe ori conduce la variante ineficiente – eficientizarea se poate realiza prin tehnica memoizării.
Un exemplu foarte simplu este șirul lui Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, … . Se observă că primii doi termeni sunt 1, iar restul termenilor se obțin însumând cei doi termeni care îl precedă. O implementare in manieră top down a acestei relații in C++ arată astfel:
​
#include <iostream>
using namespace std;
int Fib(int n) {
if (n <= 2)
return 1;
return Fib(n - 2) + Fib(n - 1);
}
int main() {
int n;
cin >> n;
cout << Fib(n);
return 0;
}
Bine înțeles, o implementare în manieră bottom up se dovedește a fi mai eficientă deoarece programul nu este nevoit să se întoarcă să rezolve subproblemele problemei actuale. Astfel, prin reținerea soluțiilor subproblemelor într-un vector, problema este rezolvată mai rapid iar numărul de operații executate de program scade. O implementare a acestei idei este următoarea:
​
#include <iostream>
using namespace std;
int main() {
int *Fib, n, i;
cin >> n;
Fib = new int [n + 1];
Fib[1] = 1;
Fib[2] = 1;
for (i = 3; i <= n; i++)
Fib[i] = Fib[i - 1] + Fib[i - 2];
cout << Fib[n] << "\n";
return 0;
}
Memoizarea
În informatică, memoizarea este o tehnică de optimizare a programelor care presupune stocarea rezultatelor apelării unor funcții costisitoare, rezolvându-se doar subproblemele care intervin in rezolvarea problemei inițiale, acestea fiind rezolvate o singură dată. Ideea care stă la baza memoizării este combinarea abordării bottom up cu cea top down. Abordarea top down rezolvă doar subproblemele necesare in rezolvarea problemei inițiale, însă subproblema este rezolvată de câte ori apare (din acest motiv o rezolvare recursivă este ineficientă în general) în timp ce abordarea bottom up rezolvă o singură dată toate subproblemele, chiar și cele care nu contribuie la soluția problemei inițiale.O rezolvare a problemei precedente folosind tehnica memoizării este următoarea:
​
#include <iostream>
using namespace std;
int *Fib;
void Fibonacci(int n) {
if (n < 3) {
return;
}
Fibonacci(n - 1);
Fib[n] = Fib[n - 1] + Fib[n - 2];
}
int main() {
int n;
cin >> n;
Fib = new int [n + 1];
Fib[1] = 1;
Fib[2] = 1;
Fibonacci(n);
cout << Fib[n] << "\n";
return 0;
}