Programare dinamica

Definiție

Programarea dinamică, sau DP (dynamic programming), este o metodă de rezolvare a unor probleme de informatică în care se cere de regulă determinarea unei valori maxime sau minime, sau numărarea elementelor unei mulțimi.

Exemplu

Problemă: Se dă o scară cu n trepte. Un individ se află în partea de jos a scării și poate să urce câte o treaptă la un pas, sau câte două trepte la un pas. În câte moduri poate urca scara?

Soluție: Dacă scara are o treaptă, ea poate fi urcată într-un singur mod, iar dacă are două trepte, sunt două modalități de a urca scara: doi pași de o treaptă sau un un pas de două trepte. Pentru n = 4, scara poate fi urcată în 5 moduri.
Este o problemă de numărare; dacă numerotăm treptele, observăm că pe treapta n se poate ajunge de pe treapta n-1 (cu un pas de o treaptă) sau de pe treapta n-2 (cu un pas de două trepte). Atunci, numărul de moduri de a urca n trepte este egal cu suma modurilor de a urca n-1 si n-2. Deci:

dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++)
   dp[n] = dp[n-1] + dp[n-2];

Putem observa că formula de mai sus este de fapt definiția șirului lui Fibonacci .

Tipar general

Aplicarea acestei tehnici de programare poate fi descompusă în următoarea secvență de pași:
  1. Identificarea structurii și a metricilor utilizate în caracterizarea soluției optime
  2. Determinarea unei metode de calcul recursiv pentru a afla valoarea fiecărei subprobleme
  3. Calcularea “bottom-up” a acestei valori (de la subproblemele cele mai mici la cele mai mari)
  4. Reconstrucția soluției optime pornind de la rezultatele obținute anterior

Probleme clasice

Clădire
Subșir crescator maximal
Rucsac