Dynamische Programmierung (DP) löst Probleme mit overlapping subproblems und optimal substructure, indem jedes Teilproblem einmal berechnet und das Ergebnis wiederverwendet wird. Die zwei Stile sind memoization (top-down) und tabulation (bottom-up).
Naive Rekursion berechnet dieselben Teilprobleme exponentiell neu. DP speichert sie zwischen, wodurch exponentielle Arbeit zu polynomieller zusammenfällt.
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 | |
|---|---|---|
| Richtung | top-down Rekursion | bottom-up Iteration |
| Berechnet | nur benötigte Zustände | alle Zustände |
| Risiko | Stack-Overflow | keines |
| Speicher | kann gekürzt werden | oft auf O(1) Zeilen reduzierbar |
Fibonacci: von O(2ⁿ) naiv zu O(n) Zeit, O(n) (oder O(1)) Speicher.
Verwende DP, wenn Teilprobleme sich überlappen. Definiere Zustand und Rekurrenz sorgfältig — das ist der schwierige Teil. Wenn Teilprobleme sich nicht überlappen, reicht einfaches Divide-and-Conquer aus.
DP wandelt unlösbare exponentielle Probleme — kürzeste Pfade, Edit Distance, Knapsack — in effiziente um.
Die Fähigkeit, Zustand und Rekurrenz zu identifizieren, ist eine der wertvollsten in Algorithmus-Interviews.
Sie liegt realen Systemen von Diff-Tools bis zur Bioinformatik-Sequenzausrichtung zugrunde.