Memoisation: Rekursive Ergebnisse zwischenspeichern

Naive rekursive Fibonacci berechnet dieselben Werte wiederholt. fib(5) ruft fib(4) und fib(3) auf; fib(4) ruft fib(3) und fib(2) auf – daher wird fib(3) zweimal berechnet. Diese Redundanz wächst exponentiell: fib(40) führt zu mehr als einer Milliarde Funktionsaufrufen. Memoisierung löst dieses Problem, indem sie jedes Ergebnis beim ersten Berechnen speichert, sodass nachfolgende Aufrufe es in O(1) abrufen, statt es erneut zu berechnen.

Fügen Sie ein memo-Dict als Parameter (oder in einer Closure) hinzu. Überprüfen Sie vor der Berechnung, ob sich die Antwort bereits in memo befindet. Falls ja, geben Sie sie sofort zurück. Falls nein, berechnen Sie sie, speichern Sie sie in memo und geben Sie sie zurück. Jedes eindeutige Teilproblem wird nun genau einmal berechnet, wodurch aus O(2^n) eine Laufzeit von O(n) und ein Speicherbedarf von O(n) für das memo-Dict sowie O(n) Stack-Speicher werden.

Python stellt @functools.lru_cache(maxsize=None) (in Python 3.9+ auch als @functools.cache verfügbar) bereit, um die Memoisierung zu automatisieren. Wenn Sie diesen Decorator über einer Funktion hinzufügen, werden alle Aufrufe anhand ihrer Argumente zwischengespeichert. maxsize=None bedeutet eine unbegrenzte Cache-Größe – jede eindeutige Argumentkombination wird zwischengespeichert. Dadurch wird jede rekursive Funktion mit nur einer Codezeile in eine memoiserte Variante umgewandelt.

LeetCode 70 „Climbing Stairs“: Sie können jeweils 1 oder 2 Stufen steigen. Wie viele Wege gibt es, Stufe n zu erreichen? Dies ist Fibonacci in einer anderen Form: ways(n) = ways(n-1) + ways(n-2). Basisfälle: ways(0) = 1 (eine Möglichkeit, auf der Ausgangsstufe zu bleiben), ways(1) = 1. Mit Memoisierung beträgt die Laufzeit O(n) und der Speicherbedarf O(n).

LeetCode 322 „Coin Change“: Gegeben sind Münzwerte und ein Zielbetrag; finden Sie die minimale Anzahl an Münzen. Top-down-Memoisierung mit Rekursion: dp(amount) = 1 + min(dp(amount - coin)) für jede gültige Münze. Der Basisfall ist: dp(0) = 0. Speichern Sie jeden Teilbetrag im Cache. Wenn ein Teilbetrag nicht erreichbar ist, geben Sie Unendlich zurück. Durch Memoisierung wird aus der exponentiellen Brute-Force-Lösung eine Laufzeit von O(amount × len(coins)).

LeetCode 139 „Word Break“: Bestimmen Sie, ob sich ein String in Wörter aus einem Wörterbuch zerlegen lässt. Die Top-down-Rekursion can_break(s, start) probiert jedes Präfix s[start:end] aus; wenn es im Wörterbuch enthalten ist und can_break(s, end) den Wert true liefert, geben Sie true zurück. Ohne Memoisierung beträgt die Laufzeit O(2^n); mit Memoisierung, bei der jeder Startindex im Cache gespeichert wird, wird sie zu O(n² × L), wobei L die maximale Wortlänge ist.

Memoisierung (Top-down) beginnt beim ursprünglichen Problem und speichert Antworten, sobald sie bei der rekursiven Lösung entdeckt werden. Sie löst nur die Teilprobleme, die tatsächlich benötigt werden. Tabulation (Bottom-up) füllt eine Tabelle von kleinen zu großen Teilproblemen vorab aus und löst alle Teilprobleme, unabhängig davon, ob sie benötigt werden. Memoisierung lässt sich leichter aus einer rekursiven Lösung ableiten; Tabulation vermeidet Begrenzungen der Rekursionstiefe und den Overhead von Funktionsaufrufen.

Viele DP-Probleme, die durch memoiserte Rekursion O(n) Speicherplatz benötigen, lassen sich auf O(1) Speicherplatz optimieren, wenn nur eine feste Anzahl vorheriger Antworten auf Teilprobleme benötigt wird. Bei Fibonacci sind nur die letzten beiden Werte relevant. Beim Treppensteigen gilt dasselbe. Zwei laufend aktualisierte Variablen ersetzen das gesamte memo-Dict oder die gesamte Tabelle.

Es gibt drei Möglichkeiten, Memoisierung manuell zu implementieren. Ein globales Dict ist einfach, belastet aber den Modul-Scope. Eine Closure kapselt den Cache innerhalb der Funktion und verhindert Leaks, erfordert jedoch einen Wrapper. @lru_cache ist die sauberste Lösung – ein einziger Decorator ersetzt den gesamten Boilerplate-Code. Beginnen Sie im Interviewkontext mit @lru_cache, es sei denn, der Interviewer bittet ausdrücklich um eine manuelle Implementierung.

Memoisierung beschleunigt nur Probleme mit überlappenden Teilproblemen – Fälle, in denen dasselbe Teilproblem mehrfach berechnet wird. Wenn jedes Teilproblem eindeutig ist (wie bei einer einfachen Baumtraversierung, bei der jeder Knoten genau einmal besucht wird), verursacht Memoisierung zusätzlichen Overhead ohne Nutzen. Außerdem kann Memoisierung keine Probleme lösen, bei denen der rekursive Baum exponentiell in der Anzahl der unterschiedlichen Teilprobleme wächst und nicht durch die Wiederverwendung von Teilproblemen entsteht – dafür ist ein völlig anderer Algorithmus erforderlich.

Wenden Sie Memoisierung an, wenn eine rekursive Lösung zwar korrekt, aber wegen redundanter Neuberechnungen langsam ist, die Funktion nur wenige unterschiedliche Argumentkombinationen besitzt und der Rückgabewert ausschließlich von den Argumenten abhängt (reine Funktion – keine Seiteneffekte, kein globaler Zustand). Prüfen Sie den Zustandsraum der Teilprobleme: Bei höchstens O(n) oder O(n²) unterschiedlichen Zuständen wandelt Memoisierung exponentielle in polynomiale Laufzeit um.

Überprüfen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie gelernt: Memoisierung speichert die Ergebnisse von Teilproblemen, um Neuberechnungen zu vermeiden, und wandelt exponentielle Rekursion in polynomiale Laufzeit um, @functools.lru_cache ist das idiomatische Python-Werkzeug und benötigt nur eine Zeile und Memoisierung (Top-down) und Tabulation (Bottom-up) sind die beiden DP-Varianten – Memoisierung lässt sich leichter ableiten, während Tabulation Probleme mit der Stack-Tiefe vermeidet. Herzlichen Glückwunsch – Sie haben die Module zu Rekursion und Hash-Maps abgeschlossen!