Programowanie dynamiczne (DP) rozwiązuje problemy z nakładającymi się podproblemami i optymalną podstrukturą, obliczając każdy podproblem raz i ponownie używając wyniku. Dwa style to memoizacja (top-down) i tabulacja (bottom-up).
Naiwna rekurencja ponownie oblicza te same podproblemy wykładniczo. DP je cache'uje, zmniejszając wykładniczą pracę do wielomianowej.
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]
| Memoizacja | Tabulacja | |
|---|---|---|
| Kierunek | rekursja top-down | iteracja bottom-up |
| Oblicza | tylko potrzebne stany | wszystkie stany |
| Ryzyko | przepełnienie stosu | brak |
| Przestrzeń | można zmniejszyć | często redukowalna do O(1) wierszy |
Fibonacci: od O(2ⁿ) naiwnego do O(n) czasu, O(n) (lub O(1)) przestrzeni.
Używaj DP gdy podproblemy się nakładają. Starannie zdefiniuj stan i rekurencję — to jest trudna część. Jeśli podproblemy się nie nakładają, zwykły divide-and-conquer wystarczy.
DP konwertuje nierozwiązalne problemy wykładnicze — najkrótsze ścieżki, odległość edycji, plecak — w efektywne.
Umiejętność identyfikowania stanu i rekurencji jest wśród najbardziej cenionych w algorytmicznych rozmowach kwalifikacyjnych.
Leży u podstaw rzeczywistych systemów od narzędzi diff do bioinformatyki wyrównywania sekwencji.