Dynamisk programmering (DP) løser problemer med overlappende delproblemer og optimal delstruktur ved å beregne hvert delproblem én gang og gjenbruke resultatet. De to stilene er memoization (top-down) og tabulation (bottom-up).
Naiv rekursjon beregner de samme delproblemene eksponentielt. DP cacher dem, og kollapser eksponentielt arbeid til polynomisk.
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 | |
|---|---|---|
| Retning | top-down rekursjon | bottom-up iterasjon |
| Beregner | kun nødvendige tilstander | alle tilstander |
| Risiko | stack overflow | ingen |
| Plass | kan trimmes | ofte reduserbar til O(1) rader |
Fibonacci: fra O(2ⁿ) naiv til O(n) tid, O(n) (eller O(1)) plass.
Bruk DP når delproblemer overlapper. Definer tilstanden og gjentakelsen nøye — det er den vanskelige delen. Hvis delproblemer ikke overlapper, er vanlig divide-and-conquer nok.
DP konverterer uhåndterlige eksponentielle problemer — korteste veier, edit-avstand, knapsack — til effektive.
Evnen til å identifisere tilstand og gjentakelse er blant de mest verdsatte i algoritmiske intervjuer.
Det ligger til grunn for virkelige systemer fra diff-verktøy til bioinformatikk-sekvensering.