🧮 Programare Dinamică

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!

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!

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
}

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];
}

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)

// 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;

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²)
}

// 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²)
}

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];
    }
}