Dynamisch programmeren (DP) lost problemen op met overlappende deelproblemen en optimale substructuur door elk deelprobleem eenmaal te berekenen en het resultaat hergebruikt. De twee stijlen zijn memoization (top-down) en tabulation (bottom-up).
Naïeve recursie berekent dezelfde deelproblemen exponentieel opnieuw. DP cacht ze en verkleint exponentieel werk tot polynomiaal.
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]
| Memoization | Tabulation | |
|---|---|---|
| Richting | top-down recursie | bottom-up iteratie |
| Berekent | alleen benodigde states | alle states |
| Risico | stack overflow | geen |
| Ruimte | kan worden gereduceerd | vaak reduceerbaar naar O(1) rijen |
Fibonacci: van O(2ⁿ) naïef naar O(n) tijd, O(n) (of O(1)) ruimte.
Gebruik DP wanneer deelproblemen overlappen. Definieer de state en recurrentie zorgvuldig — dat is het moeilijke gedeelte. Als deelproblemen niet overlappen, is gewone divide-and-conquer voldoende.
DP converteert onhanteerbare exponentiële problemen — kortste paden, edit distance, knapsack — naar efficiënte.
De vaardigheid om state en recurrentie te identificeren behoort tot de meest gewaardeerde in algoritmische interviews.
Het ondersteunt echte systemen van diff tools tot bioinformatica sequentie-alignment.