Programare dinamică

Programarea dinamică rezolvă subprobleme și le păstrează rezultatele pentru a nu le recalcula. Dacă vrem numărul de moduri de a urca $n$ trepte făcând pași de 1 sau 2, ultima mișcare vine fie de la $n-1$, fie de la $n-2$. Cu $D(0)=1$ și $D(1)=1$, obținem $D(2)=2$, $D(3)=3$, $D(4)=5$.

Programarea dinamică rezolvă o problemă prin descompunerea ei în subprobleme care se suprapun și prin memorarea răspunsurilor, ca fiecare subproblemă să fie calculată o singură dată. Se definește starea (ce înseamnă valoarea memorată, de pildă $D(i)$ = numărul de moduri de a ajunge la treapta $i$), cazurile de bază (valorile cunoscute direct) și recurența, care exprimă o stare din stările mai mici. Calculul se face în ordinea în care dependențele sunt deja cunoscute, de obicei crescător. Fără definirea precisă a stării, recurența singură nu determină rezultatul. Dacă o stare depinde numai de ultimele două, nu este nevoie să memorezi tot tabloul, iar memoria se reduce la constantă.

Exemplul 1 — urcarea pe trepte. Se urcă $n$ trepte, făcând pași de 1 sau de 2 trepte. Ultimul pas vine fie de la treapta $n-1$, fie de la $n-2$, deci $D(n)=D(n-1)+D(n-2)$, cu $D(0)=1$ și $D(1)=1$.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n = 4;
    vector<int> d(n + 1);
    d[0] = 1;
    if (n >= 1) d[1] = 1;
    for (int i = 2; i <= n; ++i)
        d[i] = d[i - 1] + d[i - 2];
    cout << d[n];
    return 0;
}

Valorile sunt $1,1,2,3,5$, deci pentru $n=4$ se afișează 5; pentru $n=7$ șirul continuă cu 8, 13, 21. Numărul de calcule este proporțional cu $n$, spre deosebire de recursia naivă, care repetă subprobleme și face un număr exponențial de apeluri.

Exemplul 2 — numărul minim de monede. Cu monedele 1, 3 și 4, $D(s)$ este numărul minim de monede care dau suma $s$. Recurența este $D(s)=1+\min D(s-m)$, luând minimul după monedele $m\le s$, cu $D(0)=0$. Valorile pentru $s=0,\dots ,6$ sunt: 0, 1, 2, 1, 1, 2, 2. Pentru $s=6$ minimul este 2 (3 + 3), în timp ce metoda greedy ar fi dat 3 monede (4 + 1 + 1). Programarea dinamică găsește optimul pentru orice sistem de monede, nu doar pentru cele „bune” pentru greedy.

int c[] = {1, 3, 4}, s = 6;
vector<int> d(s + 1, 1000000);
d[0] = 0;
for (int i = 1; i <= s; ++i)
    for (int m : c)
        if (m <= i && d[i - m] + 1 < d[i])
            d[i] = d[i - m] + 1;

După execuție, d[6] este 2.

Exemplul 3 — drumuri într-o grilă. Într-o grilă cu 3 linii și 3 coloane, mergând numai spre dreapta sau în jos de la colțul din stânga sus la fiecare celulă, numărul de drumuri este $D(i,j)=D(i-1,j)+D(i,j-1)$, cu 1 pe prima linie și prima coloană. Tabelul are liniile $(1,1,1)$, $(1,2,3)$ și $(1,3,6)$, deci până în colțul din dreapta jos sunt 6 drumuri, egal cu $C_4^2=6$. Fiecare celulă este calculată o singură dată din cele două vecine, deci timpul este proporțional cu numărul de celule.

Exemplul 4 — suma imposibilă și reconstituirea soluției. Cu monedele 2 și 5 unele sume nu se pot forma. Tabelul se începe cu o valoare foarte mare, care înseamnă „imposibil”, iar pentru $s=0,\dots ,7$ rezultă: 0, $\infty$, 1, $\infty$, 2, 1, 3, 2. Suma 3 rămâne $\infty$, pentru că nici $3-2=1$, nici o monedă de 5 nu duc la o stare posibilă. Valoarea „imposibil” se verifică înainte de adunarea lui 1, altfel apar depășiri. Tabelul dă doar numărul de monede. Dacă la fiecare sumă se memorează și ultima monedă aleasă, soluția se reconstituie de la sfârșit: pentru monedele 1, 3, 4 și $s=7$ se memorează moneda 3, apoi, pentru suma rămasă 4, moneda 4, deci $7=3+4$, în două monede.

Greșeli frecvente

• Greșit: programarea dinamică repetă calculul subproblemelor pentru a fi sigur.
  Corect: memorează răspunsurile ca să nu le recalculeze.
• Greșit: recurența determină rezultatul fără cazuri de bază.
  Corect: cazurile de bază și definiția stării sunt esențiale.
• Greșit: pentru monede, alegerea celei mai mari monede este întotdeauna optimă.
  Corect: pentru monedele 1, 3, 4 și suma 6 sunt necesare doar două monede, 3 + 3, iar greedy dă trei.

Înainte și după