Memoization & Dynamic Programming
Naive verzweigte Rekursion berechnet dieselben Teilprobleme wieder und wieder. Memoization speichert Ergebnisse — aus O(2ⁿ) wird O(n).
Fibonacci mit Memoization:
const memo = new Map();
function fib(n) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const res = fib(n - 1) + fib(n - 2);
memo.set(n, res);
return res;
}Top‑Down vs. Bottom‑Up:
- Top‑Down (Memoized Recursion): rekursiv + Cache. Easy.
- Bottom‑Up (Tabulation): iterativ Tabelle füllen. Kein Stack‑Risk.
DP‑Klassiker:
- Fibonacci, Factorial
- Coin Change
- Longest Common Subsequence
- Knapsack
- Edit Distance (Levenshtein)
- Matrix Chain Multiplication
Zurück zu Informatik