Zurück zum Fahrplan

🧠

Stufe 7

Rekursion, Backtracking & DP

Die schwersten Muster, entzaubert.

Rekursion, Backtracking und dynamische Programmierung schrecken viele ab - dabei sind sie eine Idee in drei Größen. Lerne, mit Backtracking alle Möglichkeiten zu erzeugen, und dann überlappende Rekursion mit Memoisierung und Tabellierung effizient zu machen.

5 Lektionen in dieser Stufe1 h 19 min

Erste Lektion starten

Lektionen in dieser Stufe

01
Rekursion, tief
Fortgeschritten
Basisfall und Rekursionsfall, der Call Stack und wie man einer rekursiven Lösung vertraut und sie entwirft, statt sie im Kopf zu verfolgen.
14 Min.
02
Backtracking
Experte
Systematisch Teillösungen bauen und verwerfen, um Teilmengen, Permutationen und Kombinationen zu erzeugen - und Constraint-Rätsel wie N-Damen zu lösen.
17 Min.
03
Einführung in dynamische Programmierung
Experte
Überlappende Teilprobleme und optimale Teilstruktur: exponentielle Rekursion durch Merken der Antworten (Memoisierung) in polynomiale Zeit verwandeln.
16 Min.
04
Eindimensionale DP
Experte
Die klassischen Einstiegs-DPs - Treppensteigen, House Robber, Coin Change - und wie man einen Zustand und einen Übergang definiert.
16 Min.
05
Zweidimensionale DP
Experte
Gitterpfade, längste gemeinsame Teilfolge und der Rucksack - eine Tabelle aufbauen, in der jede Zelle von früheren abhängt.
16 Min.