# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/algorithmen/README.txt]

DYNAMISCHE PROGRAMMIERUNG (DP)
==============================

Stand: 2026-01-28

WAS IST DYNAMISCHE PROGRAMMIERUNG?
----------------------------------
Dynamic Programming (DP) ist eine Methode zur Loesung komplexer Probleme, indem man sie in ueberlappende Teilprobleme zerlegt, diese *einmal* loest und die Ergebnisse *speichert*.
Motto: "Wer sich an die Vergangenheit nicht erinnert, ist verdammt, sie zu wiederholen."

UNTERSCHIED ZU DIVIDE & CONQUER
-------------------------------
- **Divide & Conquer (z.B. Merge Sort):** Teilprobleme sind unabhaengig voneinander.
- **DP:** Teilprobleme ueberlappen sich (gleiches Teilproblem wird mehrfach benoetigt).

DIE ZWEI ANSAETZE
-----------------

### 1. Top-Down (Memoization)
Wir starten beim grossen Problem und rekursieren nach unten. Ergebnisse speichern wir in einem Cache ("Memo"). Bevor wir rechnen, schauen wir im Cache nach.
- Intuitiver, wenn man Rekursion mag.
- "Lazy evaluation" (berechnet nur was noetig ist).

### 2. Bottom-Up (Tabulation)
Wir starten beim kleinsten Teilproblem und fuellen eine Tabelle auf, bis wir beim grossen Problem sind.
- Iterativ (Schleifen), kein Stack-Limit.
- Berechnet oft alle Teilprobleme (auch unnoetige).

BEISPIEL: FIBONACCI
-------------------
Naive Rekursion O(2^n) - schrecklich! `fib(50)` dauert ewig.

**Mit DP (Memoization) O(n):**
```python
memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n <= 2: return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
```
`fib(50)` dauert nun Millisekunden.

KLASSISCHE DP-PROBLEME
----------------------
- **Rucksack-Problem (Knapsack):** Wertvollste Ladung bei begrenztem Gewicht.
- **Levenshtein-Distanz:** Wie viele Edits, um String A in String B zu verwandeln? (Rechtschreibkorrektur).
- **Kuerzester Pfad im DAG:** (Gerichteter azyklischer Graph).

WANN DP VERWENDEN?
------------------
1. **Optimale Substruktur:** Die optimale Loesung setzt sich aus optimalen Teil-Loesungen zusammen.
2. **Ueberlappende Teilprobleme:** Das gleiche Unterproblem tritt immer wieder auf.

SIEHE AUCH
----------
wiki/informatik/algorithmen/komplexitaet.txt
wiki/informatik/algorithmen/rekursion.txt
