Modul 02a — Programare dinamică

De ce? Fibonacci recalculează la nesfârșit

Îți amintești din clasa a X-a (recursivitate) că fib naiv explodează. Hai să vedem DE CE — și cum DP îl salvează.

😱 naiv — recalculează totul

1int fib(int n) {

2 if (n <= 2) return 1;

3 return fib(n-1) + fib(n-2);

4} // fib(5) cheamă fib(3) de 2 ori!

😌 cu memoizare — ține minte

1int memo[100] = {0};

2int fib(int n) {

3 if (n <= 2) return 1;

4 if (memo[n]) return memo[n]; // deja calculat!

5 return memo[n] = fib(n-1) + fib(n-2);

n =

Cele două condiții ca DP să meargă: ① subprobleme care se REPETĂ (fib(3) apare de multe ori); ② subproblema optimă se construiește din subprobleme optime (fib(n) din fib(n−1) și fib(n−2)). Dacă le ai pe amândouă → DP.

Cele două stiluri: memoizare și tabelare

Aceeași idee, două direcții. Tabelarea (de jos în sus) e favorita BAC-ului — o umplem pas cu pas:

Memorizare (top-down)
Pornești de la problema mare, cobori recursiv, dar ții minte fiecare rezultat într-un vector memo[]. „Recursivitate + memorie". Natural, dar folosește stiva de apeluri.

Tabelare (bottom-up)
Umpli un tabel dp[] de la cele mai mici subprobleme spre cea mare, cu o buclă. Fără recursivitate, fără stivă — și de obicei mai rapid. Stilul de BAC.

1dp[1] = 1; dp[2] = 1;

2for (int i = 3; i <= n; i++)

3 dp[i] = dp[i-1] + dp[i-2]; // din cele două de dinainte

apasă „Pas" — tabelul se umple de la dp[1] spre dp[n], fiecare din cele două celule dinainte 👆

Plata cu monede — acolo unde Greedy dă greș

Monede de 1, 3 și 4. Vrei suma S cu cât mai PUȚINE monede. Greedy ia mereu cea mai mare — și uneori greșește. DP nu greșește niciodată.

De ce Greedy greșește la S = 6: ia 4 (cea mai mare), rămâne 2 → 1 + 1 → total 3 monede (4+1+1). Dar optimul e 2 monede: 3 + 3! Greedy nu „vede" asta pentru că nu se întoarce niciodată.

S =

dp[x] = numărul MINIM de monede pentru suma x (∞ = imposibil, deocamdată)

dp[0] = 0 (suma 0 = zero monede). Apasă „Pas" — pentru fiecare sumă x încercăm fiecare monedă 👆

1dp[0] = 0;

2for (int x = 1; x <= S; x++) {

3 dp[x] = INF;

4 for (int c : {1, 3, 4})

5 if (c <= x && dp[x-c] + 1 < dp[x])

6 dp[x] = dp[x-c] + 1; // o monedă c + optimul restului

7} // dp[S] = răspunsul

Ideea de aur: ca să plătesc x cu monede, aleg o monedă c, apoi mai am de plătit x−c — dar pe ACELA îl știu deja optim (dp[x−c])! Deci dp[x] = 1 + cel mai bun dp[x−c]. Fiecare subproblemă rezolvată o singură dată, folosită de multe ori.

Rucsacul (0/1) — a treia clasică

Ai un rucsac de capacitate G și obiecte cu greutate și valoare. Iei fiecare obiect ÎNTREG sau deloc, ca să maximizezi valoarea. DP pe două direcții.

1// dp[i][g] = valoarea maximă cu

2// primele i obiecte, capacitate g

3for (int i = 1; i <= n; i++)

4 for (int g = 0; g <= G; g++) {

5 dp[i][g] = dp[i-1][g]; // NU iau obiectul i

6 if (greut[i] <= g)

7 dp[i][g] = max(dp[i][g],

8 dp[i-1][g-greut[i]] + val[i]); // îl iau

9 }

Decizia pentru fiecare obiect: îl iau sau NU-l iau.

nu-l iau: valoarea rămâne dp[i−1][g];
îl iau (dacă încape): dp[i−1][g − greutate] + valoare;
păstrezi maximul celor două.

Greedy ar greși și aici: „ia obiectul cu valoare/kg maxim" nu dă mereu optimul la rucsacul 0/1 (nu poți lua fracțiuni). DP verifică ambele variante pentru fiecare obiect → optim garantat.

Tiparul comun al celor 3 probleme: definești CE reprezintă dp[…], scrii RELAȚIA de recurență (cum se construiește din subprobleme mai mici), stabilești CAZURILE de bază, apoi umpli tabelul în ordinea potrivită. Ăsta e tot algoritmul programării dinamice.

Fișa de sinteză

Programarea dinamică, condensată.

Când DP? subprobleme care se REPETĂ + optimul se face din optimele subproblemelor. (Altfel: Backtracking sau Greedy.)

Memoizare (top-down): recursivitate + vector memo[] care ține minte rezultatele deja calculate.

Tabelare (bottom-up): umpli dp[] cu o buclă, de la subprobleme mici spre mare. Stilul de BAC.

Rețeta: ce e dp[…] → relația de recurență → cazurile de bază → ordinea de umplere.

Monede: dp[x] = 1 + min(dp[x−c]). DP găsește 3+3 la S=6, unde Greedy ratează cu 4+1+1.

Rucsac 0/1: dp[i][g] = max(fără obiectul i, cu obiectul i). Iei sau nu iei — verifici ambele.

Exersează pe pbinfo.ro (categoria „Programare dinamică") și pe subiectele de olimpiadă: începe cu Fibonacci și monede, apoi rucsacul și cel mai lung subșir crescător.

📌 Temă pentru acasă

Trei probleme de DP, în C++.

Fibonacci cu tabelare. Citește n și afișează al n-lea termen Fibonacci umplând un vector dp[], fără recursivitate.
Plata cu monede. Se dau monedele (ex. 1, 3, 4) și suma S. Afișează numărul MINIM de monede — și, bonus, CARE monede (reconstruiește din dp[]).
Cel mai lung subșir crescător. Pentru un vector, dp[i] = lungimea celui mai lung subșir crescător care se termină la poziția i. Răspunsul = maximul din dp[]. (Clasica de olimpiadă!)

Provocare: rezolvă „plata cu monede" în DOUĂ feluri — o dată cu Backtracking (Modulul 02) și o dată cu DP. Compară numărul de operații la S mare. Vei simți în degete de ce există programarea dinamică.