Dinamičko programiranje (DP) rješava probleme s preklapajućim potproblemima i optimalnom substrukturom tako što jednom izračuna svaki potproblem i ponovno koristi rezultat. Dva su stila memoizacija (top-down) i tabeliranje (bottom-up).
Naivna rekurzija ponovno izračunava iste potproblem eksponencijalno. DP ih cachira, pretvarajući eksponencijalni rad u polinomni.
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]
| Memoizacija | Tabeliranje | |
|---|---|---|
| Smjer | top-down rekurzija | bottom-up iteracija |
| Izračunava | samo potrebna stanja | sva stanja |
| Rizik | stack overflow | nijedan |
| Prostor | može se smanjiti | često se može smanjiti na O(1) redaka |
Fibonacci: od O(2ⁿ) naivnog na O(n) vremenske, O(n) (ili O(1)) prostora.
Koristite DP kada se potproblem preklapaju. Pažljivo definirajte stanje i rekurziju — to je teški dio. Ako se potproblem ne preklapaju, obična divide-and-conquer je dovoljna.
DP pretvara neprovedive eksponencijalne probleme — najkraće putnje, uređivanje udaljenosti, ruksak — u učinkovite.
Vještina identificiranja stanja i rekurzije je među najcjenjenijima u algoritmičkim intervjuima.
Leži u temelju stvarnih sustava od diff alata do poravnanja sekvenci u bioinformatici.