Memoization oder Tabulation
Lernen Sie zwei Möglichkeiten kennen, Antworten auf Teilprobleme zwischenzuspeichern
Memoization oder Tabulation ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum überhaupt zwischenspeichern
Naive Rekursion führt dieselbe Arbeit immer wieder aus. Dynamic Programming speichert jedes Ergebnis einmal, sodass Sie es nie erneut berechnen müssen.
fib(40) # slow: recomputes endlesslyÜberlappende Teilprobleme
DP eignet sich, wenn sich ein Problem in überlappende Teilprobleme aufteilen lässt. Derselbe kleinere Fall taucht in vielen Rekursionszweigen auf.
fib(5) needs fib(3) twiceTop-down: Memoization
Memoization ist gewöhnliche Rekursion mit einem Cache. Sie berechnen Werte bei Bedarf und merken sich das Ergebnis beim ersten Auftreten jeder Eingabe.
memo = {}Einfaches Memoization in Python
Der Decorator lru_cache verwandelt langsame Rekursion mit einer einzigen Zeile in schnelles DP und speichert automatisch jeden Aufruf zwischen.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Bottom-up: Tabulation
Tabulation füllt eine Tabelle von den kleinsten Fällen bis zum Ergebnis und verwendet dafür eine Schleife statt Rekursion.
dp = [0] * (n + 1)Eine tabellarische Fibonacci-Folge
Setzen Sie die Basiswerte und lassen Sie dann jede Zelle auf die bereits berechneten Werte zugreifen. Kein Aufrufstapel, nur eine übersichtliche Schleife.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Dasselbe Ergebnis, ein anderer Stil
Memoization und Tabulation lösen dieselbe Rekurrenz. Sie unterscheiden sich nur in der Richtung: Top-down nach Bedarf oder Bottom-up in der richtigen Reihenfolge.
Wann Sie Memoization bevorzugen sollten
Verwenden Sie Memoization, wenn sich die Rekurrenz natürlich formulieren lässt und Sie möglicherweise nicht jeden Zustand benötigen.
Wann Sie Tabulation bevorzugen sollten
Wählen Sie Tabulation für enge Schleifen, um Fehler durch das Rekursionslimit zu vermeiden, und wenn Sie ohnehin die gesamte Tabelle berechnen werden.
import sys; sys.setrecursionlimit(10**6)Auf das Rekursionslimit achten
Tiefe Rekursion mit Memoization kann das Python-Rekursionslimit erreichen und bei großen Eingaben mit einem Laufzeitfehler abbrechen.
Beide haben dieselben Kosten
In beiden Fällen entsteht die Beschleunigung dadurch, dass jeder Zustand einmal gelöst wird. Die Gesamtlaufzeit entspricht der Anzahl der Zustände multipliziert mit dem Aufwand pro Zustand.
Schnelltest
Welcher Ansatz füllt eine Tabelle mit einer Schleife von unten nach oben?
Zusammenfassung: Zwei Wege, ein DP
Sie können Teilprobleme auf zwei Arten zwischenspeichern. Memoization arbeitet rekursiv von oben nach unten, Tabulation mit Schleifen von unten nach oben. Wählen Sie den Ansatz, der sich klarer liest. ✨
Häufig gestellte Fragen
Ist die Lektion „Memoization oder Tabulation“ kostenlos?
Ja — der vollständige Text von „Memoization oder Tabulation“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Memoization oder Tabulation“?
Lernen Sie zwei Möglichkeiten kennen, Antworten auf Teilprobleme zwischenzuspeichern Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Memoization oder Tabulation“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Memoization oder Tabulation
- Zustand und Übergang definieren
- Treppensteigen und Münzkombinationen
- Längste aufsteigende Teilfolge