Programare Dinamică - Introducere

Ce este Programarea Dinamică?

Programare dinamică (DP) = tehnică de rezolvare a problemelor prin descompunere în subprobleme mai mici care se repetă.

Principiu: Rezolvăm fiecare subproblemă o singură dată și stocăm rezultatul.

Când folosim DP?

1. •Substructură optimă: Soluția optimă conține soluții optime ale subproblemelor
2. •Subprobleme suprapuse: Aceleași subprobleme apar de mai multe ori

Exemplu 1: Fibonacci

Soluția recursivă (ineficientă)

Copiază
1int fib(int n) {
2    if (n <= 2) return 1;        // Caz de bază
3    return fib(n-1) + fib(n-2); // Apel recursiv
4}
5// Complexitate: O(2^n) - LENT!

Soluția DP (eficientă)

Copiază
1int fib[1001];
2
3int fibonacci(int n) {
4    fib[1] = fib[2] = 1;
5    for (int i = 3; i <= n; i++) {
6        fib[i] = fib[i-1] + fib[i-2];
7    }
8    return fib[n];
9}
10// Complexitate: O(n) - RAPID!

Exemplu 2: Problema Rucsacului (Knapsack)

Avem n obiecte cu greutăți și valori. Capacitate maximă G. Maximizează valoarea.

Copiază
1int n, G;
2int greutate[101], valoare[101];
3int dp[101][10001]; // dp[i][g] = valoare maximă cu primele i obiecte și capacitate g
4
5int rucsac() {
6    for (int i = 1; i <= n; i++) {
7        for (int g = 0; g <= G; g++) {
8            // Nu luăm obiectul i
9            dp[i][g] = dp[i-1][g];
10            
11            // Luăm obiectul i (dacă încape)
12            if (g >= greutate[i]) {
13                dp[i][g] = max(dp[i][g], dp[i-1][g-greutate[i]] + valoare[i]);
14            }
15        }
16    }
17    return dp[n][G];
18}

Exemplu 3: Subșir Crescător Maximal (LIS)

Găsește cel mai lung subșir strict crescător.

Copiază
1int v[1001], n;
2int dp[1001]; // dp[i] = lungimea LIS care se termină în v[i]
3
4int LIS() {
5    int maxLIS = 1;
6    
7    for (int i = 0; i < n; i++) {
8        dp[i] = 1; // Minim, doar elementul singur
9        
10        for (int j = 0; j < i; j++) {
11            if (v[j] < v[i]) {
12                dp[i] = max(dp[i], dp[j] + 1);
13            }
14        }
15        
16        maxLIS = max(maxLIS, dp[i]);
17    }
18    
19    return maxLIS;
20}
21// Complexitate: O(n²)

Pași pentru Rezolvare DP

1. •Identifică subproblemele
2. •Definește starea (ce reprezintă dp[i] sau dp[i][j])
3. •Găsește recurența (cum depinde dp[i] de valorile anterioare)
4. •Stabilește cazurile de bază
5. •Implementează (bottom-up sau top-down cu memoizare)

Probleme Clasice DP

• •Fibonacci
• •Problema rucsacului (0/1 și fracționar)
• •Subșir crescător maximal (LIS)
• •Cel mai lung subșir comun (LCS)
• •Problema schimbului de monede
• •Editarea șirurilor (edit distance)

Exerciții

1. •Calculează al n-lea termen Fibonacci optimizat
2. •Problema rucsacului cu obiecte date
3. •Găsește LIS pentru un vector dat

---

Stăpânește DP cu un profesor de informatică pentru olimpiadă!