Programare Dinamică¶

Ce este Programarea Dinamică?¶

Programarea dinamică (DP) este o tehnică de rezolvare a problemelor care au două proprietăți esențiale:

1. Substructură optimală — soluția optimă a problemei conține soluțiile optime ale subproblemelor
2. Subprobleme suprapuse — aceleași subprobleme sunt rezolvate de mai multe ori

DP evită recalcularea prin memorarea (caching) rezultatelor. Diferența față de Divide & Conquer: la D&C subproblemele sunt independente (nu se suprapun).

Cele două abordări¶

Top-Down (Memoizare)¶

Scriem recursiv, dar salvăm rezultatele:

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

Bottom-Up (Tabulare)¶

Construim soluțiile de la cele mai mici subprobleme în sus:

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Optimizare spațiu: adesea nu avem nevoie de tot tabelul, ci doar de ultimele câteva valori. Fibonacci se poate calcula cu $O(1)$ spațiu.

Problema 1: Longest Common Subsequence (LCS)¶

Dată două secvențe, găsește cea mai lungă subsecvență comună (nu neapărat contiguă).

Exemplu: "ABCBDAB" și "BDCAB" → LCS = "BCAB" (lungime 4)

Recurența¶

Fie $X = x_1 x_2 ... x_m$ și $Y = y_1 y_2 ... y_n$. Definim $dp[i][j]$ = lungimea LCS pentru prefixele $X[1..i]$ și $Y[1..j]$:

$$dp[i][j] = \begin{cases} 0 & \text{dacă } i = 0 \text{ sau } j = 0 \ dp[i-1][j-1] + 1 & \text{dacă } x_i = y_j \ \max(dp[i-1][j], \; dp[i][j-1]) & \text{altfel} \end{cases}$$

Intuiție: dacă ultimele caractere coincid, le includem în LCS. Dacă nu, încercăm ambele variante (excludem din X sau din Y) și o luăm pe cea mai bună.

Implementare¶

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstrucția soluției
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            result.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(result))

print(lcs("ABCBDAB", "BDCAB"))  # "BCAB"

Complexitate: $O(m \cdot n)$ timp și spațiu.

Problema 2: Knapsack 0/1¶

Avem $n$ obiecte, fiecare cu greutate $w_i$ și valoare $v_i$. Capacitatea rucsacului este $W$. Maximizăm valoarea totală fără a depăși capacitatea.

Recurența¶

$dp[i][c]$ = valoarea maximă folosind primele $i$ obiecte cu capacitate $c$:

$$dp[i][c] = \begin{cases} dp[i-1][c] & \text{dacă } w_i > c \text{ (nu încape)} \ \max(dp[i-1][c], \; dp[i-1][c - w_i] + v_i) & \text{altfel} \end{cases}$$

La fiecare obiect decidem: îl luăm sau nu îl luăm.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]  # nu luăm obiectul i
            if weights[i - 1] <= c:
                # luăm obiectul i
                with_item = dp[i - 1][c - weights[i - 1]] + values[i - 1]
                dp[i][c] = max(dp[i][c], with_item)

    return dp[n][W]

# Exemplu
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
print(knapsack(w, v, 8))  # 10 (obiecte cu w=3,v=4 și w=5,v=6)

Optimizare spațiu: O(W)¶

Observăm că linia $i$ depinde doar de linia $i-1$. Putem folosi un singur array parcurgând de la dreapta la stânga:

def knapsack_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)

    for i in range(n):
        # Parcurgem invers ca să nu folosim obiectul de două ori
        for c in range(W, weights[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i])

    return dp[W]

De ce parcurgem invers? Dacă am parcurge de la stânga la dreapta, am putea folosi obiectul $i$ de mai multe ori (aceasta ar fi varianta Unbounded Knapsack).

Problema 3: Edit Distance¶

Numărul minim de operații (inserare, ștergere, înlocuire) pentru a transforma un string în altul.

$$dp[i][j] = \begin{cases} j & \text{dacă } i = 0 \ i & \text{dacă } j = 0 \ dp[i-1][j-1] & \text{dacă } a_i = b_j \ 1 + \min(dp[i-1][j], \; dp[i][j-1], \; dp[i-1][j-1]) & \text{altfel} \end{cases}$$

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # ștergere
                    dp[i][j - 1],      # inserare
                    dp[i - 1][j - 1]   # înlocuire
                )

    return dp[m][n]

print(edit_distance("kitten", "sitting"))  # 3

Rețeta pentru Probleme DP¶

Când întâlnești o problemă nouă, urmează acești pași:

1. Definește starea — ce informație îți trebuie pentru a descrie o subproblemă? ($dp[i]$, $dp[i][j]$, etc.)
2. Scrie recurența — cum se leagă $dp[i]$ de subproblemele mai mici?
3. Stabilește cazurile de bază — valorile inițiale din tabel
4. Determină ordinea de calcul — bottom-up: asigură-te că subproblemele necesare sunt deja calculate
5. Extrage soluția — de obicei $dp[n]$ sau $dp[m][n]$
6. Reconstruiește (opțional) — parcurge tabelul invers pentru a găsi soluția efectivă

Exerciții¶

1. Coin Change: dați monezi de valori $[1, 5, 10, 25]$, care este numărul minim de monezi pentru a obține suma $S$?
2. Longest Increasing Subsequence (LIS): dată o secvență de numere, găsiți cea mai lungă subsecvență strict crescătoare. Puteți obține $O(n \log n)$?
3. Matrix Chain Multiplication: dați dimensiunile a $n$ matrici, găsiți ordinea de înmulțire care minimizează numărul total de operații
4. Transformați soluția Knapsack optimizată pentru varianta Unbounded (fiecare obiect poate fi luat de oricâte ori)