Dynamic Programming

Klassiker: Fibonacci-Zahlen. Fib(n) = Fib(n-1) + Fib(n-2). Nativ programmiert rechnet der Computer sich tot, weil er Fib(5) tausendmal neu berechnet. Mit DP speichert er Fib(5) einmal in einer Tabelle und schaut beim nächsten Mal nur nach. Aus exponentieller Laufzeit O(2^n) wird lineare Laufzeit O(n). Magie.

1. Top-Down vs. Bottom-Up

• Top-Down (Memoization): Du startest beim großen Problem ("Berechne Fib(100)") und arbeitest dich rekursiv nach unten, wobei du Zwischenergebnisse speicherst.
• Bottom-Up (Tabulation): Du startest unten ("Ich weiß Fib(1) und Fib(2)") und füllst eine Tabelle aufwärts bis 100. Das spart den Rekursions-Stack (kein Stack Overflow).

2. Anwendungen

• Kürzester Pfad im Navi (Dijkstra/Bellman-Ford nutzen DP-Konzepte).
• Rechtschreibkorrektur (Levenshtein-Distanz): Wie viele Buchstaben muss ich ändern, um aus "Hallo" "Hello" zu machen?

  Musterantwort: Beginne mit dem konkreten Fall, prüfe die Fakten und erkläre den Begriff daran. Für diesen Abschnitt gilt: Klassiker: Fibonacci-Zahlen. Fib(n) = Fib(n-1) + Fib(n-2). Nativ programmiert rechnet der Computer sich tot, weil er Fib(5) tausendmal neu berechnet. Mit DP speichert er Fib(5) einmal in einer Tabelle und schaut beim nächsten Mal nur nach. Aus exponentieller Laufzeit O(2^n) wird lineare Laufzeit O(n). Magie.
• Textumbruch in Word (Knuth-Plass Algorithmus).

1. Zustandsübergangsgleichung (Bellman Equation)

Das mathematische Herz von DP. Wenn Richard Bellman 1953 das Prinzip bewies, formulierte er das Prinzip der Optimalität: "Eine optimale Politik hat die Eigenschaft, dass, was auch immer der Anfangszustand und die Anfangsentscheidung sind, die verbleibenden Entscheidungen eine optimale Politik in Bezug auf den Zustand bilden müssen, der sich aus der ersten Entscheidung ergibt." In Code übersetzt man dies rigoros in eine recurrence relation: $V(s) = \max_a (R(s, a) + \gamma V(s'))$. Dieses Prinzip treibt heute tiefgreifend Reinforcement Learning (Q-Learning) an, da Agenten Pfad-Belohnungen in Markov Decision Processes exakt nach dieser DP-Gleichung rückwärts auflösen.

2. State-Space Explosion vs Dimensionalität

Der feindliche Endgegner der Dynamischen Programmierung ist der "Fluch der Dimensionalität". Memoization funktioniert brillian, wenn der State eindimensional ist (z.B. Index $i$). Braucht das Problem aber 5 Parameter (Zeit, Ort, Rucksack-Gewicht, Item-Klasse, Treibstoff), explodiert die DP-Tabelle $\mathcal{O}(N \times M \times P \times \dots)$. Aus "Ich speichere das Zwischenergebnis im RAM" wird plötzlich ein multidimensionaler Array, der 500 Terabyte Speicher frisst. In der Realität weicht man dann auf Approximate Dynamic Programming aus, bei dem neuronale Netze die gigantische Look-Up Table schätzen, statt sie physisch zu allozieren.

3. Space Optimization (Sliding Window)

In LeetCode-Interviews (und Kernel-C++ Codes) verlangt man oft die "Space Optimization" von Tabulation. Bei Fibonacci $F(n) = F(n-1) + F(n-2)$ berechnet Bottom-Up ein Array von Größe 100. Der Profi sieht sofort: Für $F(100)$ brauche ich nur Step 99 und 98. Die Resultate 1 bis 97 sind in der Array-Memory unnötiger Müll. Man reduziert den $\mathcal{O}(N)$ Space zu $\mathcal{O}(1)$ Space, indem man nur drei Integer-Variablen (a, b, current) im CPU-Register rotieren lässt. Das rettet CPU-Caches bei echten Backend-Anwendungen enorm.