🧮 Programare Dinamică

Capitolul 9 — De la recursivitate la DP: memoizare, tabel, LIS, triunghi

DPMemoizareLISFibonacciTriunghi Pascal
📖 12 min
0
🧮

Fibonacci — de la O(2ⁿ) la O(n)

💡 Ce este programarea dinamică?

Programarea dinamică (DP) rezolvă problemele complexe spărgându-le în subprobleme mai mici și stocând rezultatele pentru a nu le recalcula. Se aplică când există subprobleme suprapuse — adică aceeași subproblemă apare de mai multe ori în recursivitate.

Problema: recursivitate naivă — O(2ⁿ)

// Fibonacci recursiv NaIV — calculează de mii de ori aceleași valori!
int fib(int n) {
    if (n <= 1) return n;          // caz de bază
    return fib(n-1) + fib(n-2);  // O(2^n) apeluri!
}
// fib(40) = ~2 miliarde operații → prea lent!
Problema: fib(5) calculează fib(3) de 2 ori, fib(2) de 3 ori. La n=40, se fac ~2 miliarde de apeluri pentru valori deja cunoscute.

Soluția DP: tabel — O(n)

int dp[100];   // dp[i] = al i-lea număr Fibonacci

void calcFibDP(int n) {
    dp[0] = 0;  dp[1] = 1;   // cazuri de bază
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];  // fiecare valoare calculată o singură dată
}
// fib(40) = 8 operații, nu 2 miliarde!
Recursiv naiv

Complexitate: O(2ⁿ)
n=40 → ~2 miliarde ops
Lent, inacceptabil la BAC

DP (tabel)

Complexitate: O(n)
n=40 → 40 operații
Rapid, eficient

Regula de aur DP: Dacă o funcție recursivă recalculează aceleași valori, transformă-o în DP — salvează rezultatele într-un tablou.
💾

Memoizare (DP top-down)

Memoizarea adaugă un cache funcției recursive existente. La primul apel, calculează și salvează. La apelurile ulterioare, returnează direct valoarea salvată.

int memo[10001];   // inițializat cu -1 = "necalculat"

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // deja calculat → returnează direct
    memo[n] = fib(n-1) + fib(n-2);    // calculează și salvează
    return memo[n];
}

int main() {
    // Inițializare obligatorie!
    fill(memo, memo + 10001, -1);
    cout << fib(100) << endl;  // O(n) apeluri în total
}
Template general memoizare: 
int cache[MAXN];
memset(cache, -1, sizeof(cache));  // sau fill()

int solve(int n) {
    if (/* caz de baza */) return /* valoare_baza */;
    if (cache[n] != -1) return cache[n];
    cache[n] = /* calcul bazat pe apeluri recursive */;
    return cache[n];
}
Avantaj

Cod simplu, se pornește de la soluția recursivă existentă

Dezavantaj

Stiva de recursivitate — stack overflow pentru n mare

Complexitate

Timp: O(n) · Spațiu: O(n) pentru cache + O(n) stack

📊

DP tabelar (bottom-up)

DP bottom-up construiește tabelul de la cazuri mici la mari, fără recursivitate. Este mai eficient ca memorie și evită stack overflow.

// Fibonacci bottom-up cu tabel complet — O(n) timp, O(n) spațiu
int dp[100001];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];
cout << dp[n] << endl;

// Optimizat cu 2 variabile — O(n) timp, O(1) spațiu!
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b; b = c;
}
cout << b << endl;  // Fibonacci(n)
Număr de modalități de a urca n trepte (1 sau 2 trepte odată) — problemă clasică DP: 
// dp[i] = nr. moduri de a ajunge la treapta i
int dp[1001];
dp[0] = 1;  // 0 trepte: 1 mod (nu faci nimic)
dp[1] = 1;  // 1 treaptă: 1 mod (un pas de 1)
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];  // vin din treapta i-1 (1 pas) sau i-2 (2 pași)
cout << dp[n] << endl;
Structura oricărei soluții DP:
1. Definește dp[i] (ce reprezintă)
2. Cazuri de bază (dp[0], dp[1], ...)
3. Relație de recurență (cum dp[i] depinde de dp[j], j<i)
4. Răspunsul (dp[n] sau max din dp[])
📈

Cel mai lung subșir strict crescător (LIS)

📖 Definiție

Dat un vector v[1..n], găsim cel mai lung subșir de indici i₁ < i₂ < ... < iₖ cu v[i₁] < v[i₂] < ... < v[iₖ]. Elementele selectate nu trebuie să fie consecutive în vector.

Exemplu: v = [3, 1, 4, 1, 5, 9, 2, 6] → LIS = [1, 4, 5, 9] sau [1, 4, 5, 6], lungime = 4

Soluție DP — O(n²)

// dp[i] = lungimea celui mai lung subșir crescător care se termină la v[i]
int v[1001], dp[1001], n;

int lisLength() {
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;  // minim: subșir cu un singur element
        for (int j = 1; j < i; j++)
            if (v[j] < v[i])               // v[j] poate precede v[i]
                dp[i] = max(dp[i], dp[j] + 1);
    }
    int lis = 0;
    for (int i = 1; i <= n; i++)
        lis = max(lis, dp[i]);
    return lis;  // O(n²)
}
Trasare pe exemplu: v = [3, 1, 4, 1, 5]
dp[1]=1 (v[1]=3), dp[2]=1 (v[2]=1), dp[3]=2 (1<4: dp[2]+1),
dp[4]=1 (v[4]=1, nimic mai mic), dp[5]=3 (4<5: dp[3]+1)
→ LIS = max(1,1,2,1,3) = 3
LIS clasic — O(n²)

Două bucle imbricate. Suficient pentru n≤5000 la BAC.

LIS optimizat — O(n log n)

Folosește Binary Search pentru n ≤ 10⁵. Nu e cerut la BAC M-I standard.

🔺

Triunghi de numere — suma maximă

📖 Problema

Dat un triunghi de numere cu n rânduri, se coboară de la vârf (rândul 1) la baza (rândul n), la fiecare pas mișcând-ne pe același indice sau indicele+1. Găsim drumul cu suma maximă.

// Exemplu triunghi (n=4):
//    7
//   3 8
//  8 1 0
// 2 7 4 4
// Drum optim: 7→8→1→7 = 23 (sau 7→3→8→7=25)

int t[101][101], dp[101][101], n;

// DP bottom-up (de la baza spre vârf)
void triunghi() {
    // Copiem baza ca stare inițială
    for (int j = 1; j <= n; j++)
        dp[n][j] = t[n][j];

    // Urcăm de la rândul n-1 spre rândul 1
    for (int i = n-1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            dp[i][j] = t[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

    cout << "Suma maxima: " << dp[1][1] << endl;  // O(n²)
}
Alternativ (top-down): dp[i][j] = t[i][j] + max(dp[i-1][j-1], dp[i-1][j]), pornind de la vârf. Ambele variante sunt echivalente.
🎮

Demo interactiv — Fibonacci DP tabelar

Urmărește cum se construiește tabelul DP pentru Fibonacci pas cu pas. Fiecare celulă se calculează o singură dată — O(n) în loc de O(2ⁿ).

Normal
📊 Tabelul DP
📈 Statistici
Operații DP: 0
Operații recursive: 0
Aștept...
Caz de bază Calculat acum Folosește dp[i-1]+dp[i-2]
🧩

Probleme rezolvate — programare dinamică

5 probleme DP clasice, fiecare cu starea, recurența și cazurile de bază explicate.

1 Urcarea scărilor (1 sau 2 trepte) Ușor
În câte moduri poți urca o scară cu n trepte, dacă la fiecare pas urci 1 sau 2 trepte?
Intrare:
5
Ieșire:
8
💡 Vezi soluția 
long long dp[100];
int main() {
    int n; cin >> n;
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    cout << dp[n];
}

Recurența: ca să ajungi la treapta i poți veni de la i−1 (pas de 1) sau i−2 (pas de 2). E exact Fibonacci! Stare: dp[i] = nr. modurilor de a ajunge la treapta i.

2 Sumă maximă în subvector contiguu (Kadane) Mediu
Dat un vector cu numere (pozitive și negative), găsește suma maximă a unui subvector contiguu nevid.
Intrare:
9
-2 1 -3 4 -1 2 1 -5 4
Ieșire:
6
💡 Vezi soluția 
int n, a[100005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int best = a[1], cur = a[1];
    for (int i = 2; i <= n; i++) {
        cur = max(a[i], cur + a[i]);   // extind sau restart
        best = max(best, cur);
    }
    cout << best;
}

Algoritmul lui Kadane (O(n)): la fiecare poziție alegem fie să continuăm subvectorul curent, fie să pornim unul nou de la a[i]. Pe exemplu: 4 + (−1) + 2 + 1 = 6.

3 Rest cu monede (nr. moduri) Mediu
Date n monede cu valori distincte și o sumă S, calculează în câte moduri poți forma S (fiecare monedă se poate folosi de oricâte ori). Două moduri sunt diferite dacă diferă numărul de monede dintr-o anumită valoare.
Intrare:
3 4
1 2 3
Ieșire:
4
💡 Vezi soluția 
int n, S, c[50];
long long dp[10005];
int main() {
    cin >> n >> S;
    for (int i = 1; i <= n; i++) cin >> c[i];
    dp[0] = 1;                  // 1 mod să faci 0: nu pui nimic
    for (int i = 1; i <= n; i++)
        for (int s = c[i]; s <= S; s++)
            dp[s] += dp[s - c[i]];
    cout << dp[S];
}

Cheia: bucla pe monede e exterioară — astfel evităm să numărăm aceeași combinație în ordini diferite. Pentru {1,2,3} și S=4: {1+1+1+1}, {1+1+2}, {2+2}, {1+3} = 4 moduri.

4 Numărul de drumuri într-o grilă Mediu
Pe o grilă n × m pornești din (1,1) și vrei să ajungi în (n,m), mergând doar la dreapta sau în jos. Câte drumuri distincte există?
Intrare:
3 4
Ieșire:
10
💡 Vezi soluția 
long long dp[25][25];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) dp[i][1] = 1;
    for (int j = 1; j <= m; j++) dp[1][j] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= m; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    cout << dp[n][m];
}

Recurența: la celula (i,j) poți ajunge din (i−1,j) — venind de sus — sau din (i,j−1) — venind din stânga. Cazurile de bază: prima linie și prima coloană au câte un singur drum (mereu jos sau mereu dreapta).

5 Rucsac 0/1 (knapsack) Dificil
Ai n obiecte, fiecare cu o greutate w[i] și valoare v[i], și un rucsac de capacitate W. Maximizează valoarea totală selectând obiecte (fiecare 0 sau 1 dată).
Intrare:
4 7
2 3
3 4
4 5
5 6
Ieșire:
9
💡 Vezi soluția 
int n, W, w[105], v[105];
int dp[105][10005];
int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i-1][c];                 // nu luăm obiectul
            if (c >= w[i])
                dp[i][c] = max(dp[i][c], dp[i-1][c-w[i]] + v[i]);
        }
    cout << dp[n][W];
}

Stare: dp[i][c] = valoarea maximă folosind primele i obiecte și capacitate c. Decizie: îl luăm pe i (dacă încape) sau nu. Pe exemplu: obiectele 3 (val 3+4=7) sau 4 (val 4+5=9) — răspuns 9. Complexitate O(n·W).

💪 Mai multă practică în secțiunea BAC de mai jos.
🎓

Probleme tip BAC — Programare Dinamică

Problema 1: Cel mai lung subșir de valori egale consecutive

// Cerință: găsește lungimea maximă a unui bloc de valori egale în șir
int v[1001], n;
int maxLen = 1, cur = 1;
for (int i = 2; i <= n; i++) {
    if (v[i] == v[i-1]) cur++;
    else cur = 1;
    maxLen = max(maxLen, cur);
}
cout << maxLen;

Problema 2: Fibonacci(n) modulo 10⁹+7

const int MOD = 1000000007;
long long dp[1000001];

dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = (dp[i-1] + dp[i-2]) % MOD;
cout << dp[n];

Problema 3: LIS — lungime și reconstituire

int v[1001], dp[1001], prev_idx[1001], n;

void lis_reconstituire() {
    int best_end = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; prev_idx[i] = -1;
        for (int j = 1; j < i; j++)
            if (v[j] < v[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev_idx[i] = j;
            }
        if (dp[i] > dp[best_end]) best_end = i;
    }
    // Reconstituire (de la coadă spre cap)
    int idx = best_end;
    while (idx != -1) {
        cout << v[idx] << " ";
        idx = prev_idx[idx];
    }
}
Subiecte unde apare DP la BAC

Fibonacci, nr. modalități de dispunere, LIS, suma maximă pe drum în triunghi, probleme de numărare cu restricții

Identificare rapidă

Dacă problema cere „numărul de moduri" sau „cea mai bună/lungă cale" — gândește-te la DP!