Programarea dinamică (DP) rezolvă probleme cu subprobleme suprapuse și structură de suboptimalitate calculând fiecare subproblemă o singură dată și reutilizând rezultatul. Cele două stiluri sunt memoizarea (top-down) și tabularea (bottom-up).
Recursia naivă recalculează aceleași subprobleme exponențial. DP le pune în cache, transformând munca exponențială în una polinomială.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoizare | Tabulare | |
|---|---|---|
| Direcție | recursiune top-down | iterație bottom-up |
| Calculează | doar stări necesare | toate stările |
| Risc | stack overflow | niciun |
| Spațiu | poate fi redus | adesea reductibil la O(1) rânduri |
Fibonacci: de la O(2ⁿ) naiv la O(n) timp, O(n) (sau O(1)) spațiu.
Foloseşte DP când subproblemele se suprapun. Definește starea și recurența cu grijă — aceasta este partea dificilă. Dacă subproblemele nu se suprapun, divide-and-conquer simplu este suficient.
DP transformă problemele exponențiale intractabile — căi scurte, distanța de editare, rucsac — în probleme eficiente.
Capabilitatea de a identifica starea și recurența este printre cele mai apreciate în interviurile de algoritmi.
Este la baza sistemelor reale, de la uneltele diff la alinierea secvențelor în bioinformatică.