Algorithmen4Lerneinheiten21minStand30.05.2026

Dynamische Programmierung.

Fachliche Qualität

Noch nicht klassifiziertNoch nicht geprüft.

Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

Zur KategorieAlgorithmen.Mehr Themen entdeckenZum Themen-Hub.

Dynamische Programmierung, Algorithmen · UniProMax

Du sollst die 30. Fibonacci-Zahl berechnen. Naiver Code: 1,3 Millionen rekursive Aufrufe. Mit dynamischer Programmierung: 30 Aufrufe. Das ist die Macht von DP — du speicherst Zwischenergebnisse, damit du sie nicht doppelt berechnest. Klausur-Pflicht in 14/17 WInf-Algo-Klausuren, eines der mächtigsten algorithmischen Konzepte überhaupt.

Dynamische Programmierung (DP): Zerlege ein Problem in überlappende Teilprobleme, löse jedes Teilproblem nur einmal und speichere das Ergebnis. Setze die Teilergebnisse zu einer Gesamtlösung zusammen.

Ein Problem ist DP-fähig, wenn es zwei Eigenschaften hat:

Optimale Substruktur: Die optimale Lösung lässt sich aus optimalen Lösungen der Teilprobleme zusammenbauen.
Überlappende Teilprobleme: Dieselben Teilprobleme tauchen bei der Rekursion mehrfach auf.

Wenn nur (1) gilt, ohne (2), reicht Divide-and-Conquer (z.B. Mergesort). DP brauchst du genau wenn Teilprobleme sich wiederholen.

Naiv (exponentiell):

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(5) ruft fib(4) und fib(3). fib(4) ruft fib(3) und fib(2). fib(3) wird also doppelt berechnet — und exponentiell oft bei größeren n. Laufzeit: $O(2^n)$ .

Mit DP (Memoization, Top-Down):

int[] memo = new int[n + 1];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

Jedes fib(k) wird nur einmal berechnet. Laufzeit: $O(n)$ .

Mit DP (Tabulation, Bottom-Up):

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Beide DP-Varianten sind $O(n)$ . Bottom-Up spart den Rekursions-Overhead.

Memoization (Top-Down)

Rekursive Lösung, aber jedes Ergebnis wird in einer Tabelle gespeichert. Beim zweiten Aufruf direkt zurück.

Pro: Natürliche Übersetzung der Rekursion. Du berechnest nur was wirklich gebraucht wird. Contra: Rekursions-Overhead (Stack). Bei sehr großen n: Stack-Overflow.

Tabulation (Bottom-Up)

Iterativ. Du baust die Tabelle von den kleinsten Teilproblemen hoch.

Pro: Kein Stack-Overhead. Oft schneller in der Praxis. Contra: Du musst die Reihenfolge kennen. Berechnet manchmal mehr als nötig.

1. Rucksack-Problem (0/1 Knapsack)

Gegeben $n$ Gegenstände mit Gewicht $w_i$ und Wert $v_i$ , ein Rucksack mit Kapazität $W$ . Maximiere den Gesamtwert.

DP-Tabelle: $dp[i][c]$ = max. Wert mit ersten $i$ Items und Kapazität $c$ .

$dp[i][c] = \max(dp[i-1][c], dp[i-1][c - w_i] + v_i)$

Laufzeit: $O(n \cdot W)$ . Pseudo-polynomial (W ist die Zahl, nicht log W).

2. Längste gemeinsame Teilfolge (LCS)

Gegeben zwei Strings. Finde die längste Teilfolge, die in beiden vorkommt.

$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{wenn } s_i = t_j \\ \max(dp[i-1][j], dp[i][j-1]) & \text{sonst} \end{cases}$

Laufzeit: $O(m \cdot n)$ .

3. Edit-Distanz (Levenshtein)

Wie viele Operationen (Insert/Delete/Replace) braucht man, um String A in String B zu verwandeln?

Standard-DP-Anwendung, $O(m \cdot n)$ .

4. Münzwechsel

Gegeben Münz-Werte $\{c_1, c_2, \ldots, c_n\}$ und Zielbetrag $S$ . Minimiere die Anzahl Münzen.

$dp[s] = \min_{c_i \leq s} (dp[s - c_i] + 1)$

5. Längste aufsteigende Teilfolge (LIS)

$O(n^2)$ naiv, $O(n \log n)$ mit Binary Search.

Greedy: trifft lokal beste Entscheidung, ohne zurückzuschauen. Schnell, aber findet manchmal nicht das Optimum.

DP: prüft alle relevanten Optionen, garantiert das Optimum.

Beispiel: Münzwechsel mit Münzen $\{1, 5, 10, 25\}$ für 30 Cent.

Greedy: 25 + 5 = 2 Münzen ✓ (zufällig optimal)

Aber bei $\{1, 6, 10\}$ für 12 Cent:

Greedy: 10 + 1 + 1 = 3 Münzen
DP: 6 + 6 = 2 Münzen ✓

Greedy ist nicht immer optimal — DP ist es.

1. Überlappende Teilprobleme + optimale Substruktur → DP geeignet.

2. Memoization für rekursive Lösungen, Tabulation für iterative. Wenn beides geht, ist Bottom-Up oft schneller.

3. DP-Tabelle aufzeichnen. Bei Klausur-Aufgaben hilft eine explizite Tabelle (Zeilen = i, Spalten = j) — Punkteklau-frei.

4. Rekurrenz hinschreiben + Basis-Fall. Standard-Klausur-Form: $dp[i] = \ldots$ + $dp[0] = \ldots$ .

5. Komplexität = Anzahl Zustände × Aufwand pro Übergang. Rucksack: $O(n \cdot W)$ , LCS: $O(m \cdot n)$ .

1. Memoization vergessen. Wer "DP" macht aber die Memo-Tabelle nicht checkt, hat einfach nur eine teure Rekursion.

2. Falsche Reihenfolge bei Tabulation. $dp[i]$ braucht $dp[i-1]$ und $dp[i-2]$ → musst aufsteigend befüllen. Bei 2D-Tabellen: Reihenfolge der Schleifen wichtig.

3. Basis-Fälle falsch. $dp[0]$ und $dp[1]$ explizit setzen, sonst Müll in der Tabelle.

4. Rucksack als 1D-Array. 2D-Tabelle ist klassisch, 1D-Optimierung möglich aber gefährlich (richtung der Schleife muss umgekehrt sein, um Doppel-Zählung zu vermeiden).

5. DP für nicht-DP-Probleme. Wenn keine überlappenden Teilprobleme: Divide-and-Conquer reicht (z.B. Mergesort, Binäre Suche). DP wäre Overkill.

Geh Schritt für Schritt durch die Fibonacci-DP-Tabelle und sieh, wie sie sich aufbaut:

Naive Rekursion zeigt die exponentielle Anzahl von Aufrufen
Memoization (Top-Down) baut die Tabelle entlang der Rekursion auf
Tabulation (Bottom-Up) befüllt die Tabelle iterativ von links nach rechts

Beobachte: bei naiver Rekursion explodieren die Aufrufe, bei DP wächst die Tabelle linear.

Lade Visualisierung...

Klausur-Tipp: Bei DP-Aufgaben IMMER zuerst die Rekurrenz aufschreiben ( $dp[i] = \ldots$ + Basis-Fall). Dann eine Tabelle anlegen und die ersten Werte explizit ausrechnen. Punkteklau-sicher in Klausuren.

Anmelden, um den Fortschritt zu speichern.

Nächster Schritt

Wenn du fertig bist: jetzt üben.

Aktives Abrufen festigt Wissen schneller als nochmal lesen.

Die Idee in einem Satz

Dynamische Programmierung (DP): Zerlege ein Problem in überlappende Teilprobleme, löse jedes Teilproblem nur einmal und speichere das Ergebnis. Setze die Teilergebnisse zu einer Gesamtlösung zusammen.

Voraussetzungen (Klausur-Pflichtwissen)

Ein Problem ist DP-fähig, wenn es zwei Eigenschaften hat:

Optimale Substruktur: Die optimale Lösung lässt sich aus optimalen Lösungen der Teilprobleme zusammenbauen.
Überlappende Teilprobleme: Dieselben Teilprobleme tauchen bei der Rekursion mehrfach auf.

Wenn nur (1) gilt, ohne (2), reicht Divide-and-Conquer (z.B. Mergesort). DP brauchst du genau wenn Teilprobleme sich wiederholen.

Beispiel: Fibonacci

Naiv (exponentiell):

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(5) ruft fib(4) und fib(3). fib(4) ruft fib(3) und fib(2). fib(3) wird also doppelt berechnet — und exponentiell oft bei größeren n. Laufzeit: O(2ⁿ).

Mit DP (Memoization, Top-Down):

int[] memo = new int[n + 1];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

Jedes fib(k) wird nur einmal berechnet. Laufzeit: O(n).

Mit DP (Tabulation, Bottom-Up):

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Beide DP-Varianten sind O(n). Bottom-Up spart den Rekursions-Overhead.

Zwei DP-Stile

Memoization (Top-Down)

Rekursive Lösung, aber jedes Ergebnis wird in einer Tabelle gespeichert. Beim zweiten Aufruf direkt zurück.

Pro: Natürliche Übersetzung der Rekursion. Du berechnest nur was wirklich gebraucht wird. Contra: Rekursions-Overhead (Stack). Bei sehr großen n: Stack-Overflow.

Tabulation (Bottom-Up)

Iterativ. Du baust die Tabelle von den kleinsten Teilproblemen hoch.

Pro: Kein Stack-Overhead. Oft schneller in der Praxis. Contra: Du musst die Reihenfolge kennen. Berechnet manchmal mehr als nötig.

Standard-DP-Probleme (klausur-relevant)

1. Rucksack-Problem (0/1 Knapsack)

Gegeben n Gegenstände mit Gewicht w_i und Wert v_i, ein Rucksack mit Kapazität W. Maximiere den Gesamtwert.

DP-Tabelle: dp[i][c] = max. Wert mit ersten i Items und Kapazität c.

dp[i][c] = max(dp[i-1][c], dp[i-1][c - w_i] + v_i)

Laufzeit: O(n · W). Pseudo-polynomial (W ist die Zahl, nicht log W).

2. Längste gemeinsame Teilfolge (LCS)

Gegeben zwei Strings. Finde die längste Teilfolge, die in beiden vorkommt.

dp[i][j] = dp[i-1][j-1] + 1 wenn wenn s_i = t_j; max(dp[i-1][j], dp[i][j-1]) wenn sonst

Laufzeit: O(m · n).

3. Edit-Distanz (Levenshtein)

Wie viele Operationen (Insert/Delete/Replace) braucht man, um String A in String B zu verwandeln?

Standard-DP-Anwendung, O(m · n).

4. Münzwechsel

Gegeben Münz-Werte \c₁, c₂, ..., c_n\ und Zielbetrag S. Minimiere die Anzahl Münzen.

dp[s] = min_(c_i ≤ s) (dp[s - c_i] + 1)

5. Längste aufsteigende Teilfolge (LIS)

O(n²) naiv, O(n log n) mit Binary Search.

DP vs. Greedy

Greedy: trifft lokal beste Entscheidung, ohne zurückzuschauen. Schnell, aber findet manchmal nicht das Optimum.

DP: prüft alle relevanten Optionen, garantiert das Optimum.

Beispiel: Münzwechsel mit Münzen \1, 5, 10, 25\ für 30 Cent.

Greedy: 25 + 5 = 2 Münzen ✓ (zufällig optimal)

Aber bei \1, 6, 10\ für 12 Cent:

Greedy: 10 + 1 + 1 = 3 Münzen
DP: 6 + 6 = 2 Münzen ✓

Greedy ist nicht immer optimal — DP ist es.

Klausur-Faustregeln

1. Überlappende Teilprobleme + optimale Substruktur → DP geeignet.

2. Memoization für rekursive Lösungen, Tabulation für iterative. Wenn beides geht, ist Bottom-Up oft schneller.

3. DP-Tabelle aufzeichnen. Bei Klausur-Aufgaben hilft eine explizite Tabelle (Zeilen = i, Spalten = j) — Punkteklau-frei.

4. Rekurrenz hinschreiben + Basis-Fall. Standard-Klausur-Form: dp[i] = ... + dp[0] = ....

5. Komplexität = Anzahl Zustände × Aufwand pro Übergang. Rucksack: O(n · W), LCS: O(m · n).

Häufige Stolpersteine

1. Memoization vergessen. Wer "DP" macht aber die Memo-Tabelle nicht checkt, hat einfach nur eine teure Rekursion.

2. Falsche Reihenfolge bei Tabulation. dp[i] braucht dp[i-1] und dp[i-2] → musst aufsteigend befüllen. Bei 2D-Tabellen: Reihenfolge der Schleifen wichtig.

3. Basis-Fälle falsch. dp[0] und dp[1] explizit setzen, sonst Müll in der Tabelle.

4. Rucksack als 1D-Array. 2D-Tabelle ist klassisch, 1D-Optimierung möglich aber gefährlich (richtung der Schleife muss umgekehrt sein, um Doppel-Zählung zu vermeiden).

5. DP für nicht-DP-Probleme. Wenn keine überlappenden Teilprobleme: Divide-and-Conquer reicht (z.B. Mergesort, Binäre Suche). DP wäre Overkill.

Teil 3·Quiz / Klausurfragen

Praxis-Übung

Dynamische Programmierung — Praxis-Übung

6 Aufgaben zu DP-Konzepten, Memoization, Tabulation, klassischen Problemen.

Klausurfragen mit Lösungen (6)

F1.Welche Eigenschaft muss ein Problem haben, damit DP sinnvoll ist?

Antwort: Optimale Substruktur UND überlappende Teilprobleme

Erklärung: BEIDES nötig: (1) Optimum aus Teil-Optima zusammenbaubar, (2) Teilprobleme tauchen mehrfach auf. Nur (1) ohne (2) → Divide-and-Conquer reicht. Greedy ist ein anderes Paradigma.

F2.Was ist die Laufzeit der naiven rekursiven Fibonacci-Berechnung?

Antwort: O(2ⁿ) (exponentiell)

Erklärung: Naive Rekursion fib(n) = fib(n-1) + fib(n-2) verzweigt sich → O(2ⁿ). fib(30) braucht ca. 1,3 Mio Aufrufe. Mit DP (Memoization oder Tabulation): O(n).

F3.Memoization ist Top-Down DP, Tabulation ist Bottom-Up DP.

Antwort: Wahr

Erklärung: RICHTIG. Memoization: rekursiv von oben (Problem → Teilprobleme), Ergebnisse in Tabelle speichern. Tabulation: iterativ von unten (kleinste Teilprobleme zuerst), Tabelle iterativ befüllen.

Typ: Wahr/Falsch

F4.Welche der folgenden Probleme ist KEIN klassisches DP-Problem?

Antwort: Binäre Suche

Erklärung: Binäre Suche ist Divide-and-Conquer, NICHT DP — keine überlappenden Teilprobleme, jeder Schritt halbiert das Problem in nur ein Teilproblem. Rucksack, LCS, Edit-Distanz sind DP-Klassiker.

F5.Welche Aussagen über DP sind RICHTIG?

Richtige Antworten: Memoization spart Berechnungen durch Caching; Tabulation berechnet manchmal mehr Werte als nötig; DP findet immer das Optimum (bei korrekter Rekurrenz); Knapsack hat Laufzeit O(n · W)

Erklärung: Richtig: Memoization = Caching, Tabulation überberechnet manchmal, DP = optimal, Knapsack pseudo-polynomial O(n·W). Falsch: DP kann rekursiv (Memoization) oder iterativ (Tabulation) sein; Greedy ist schneller ABER findet nicht immer das Optimum.

Typ: Multi-Select

F6.Ordne DP-Problem der typischen Laufzeit zu:

Zuordnungen:

Fibonacci mit DP → O(n)
0/1-Knapsack → O(n · W)
Längste gemeinsame Teilfolge (LCS) → O(m · n)
Naive Fibonacci → O(2ⁿ)

Erklärung: Standard-Laufzeiten. Fibonacci: linear. Knapsack: pseudo-polynomial. LCS: quadratisch. Naive: exponentiell.

Typ: Zuordnung

Teil 4·Quiz / Klausurfragen

Klausur-Quiz

Klausurfragen mit Lösungen (6)

F1.Was bedeutet 'pseudo-polynomial' bei der Knapsack-Laufzeit O(n · W)?

Antwort: Die Laufzeit ist polynomial im Wert W, nicht in log(W)

Erklärung: Eingabe-Länge einer Zahl W ist log(W) Bits. Polynomial in der Eingabe-Länge wäre O(n · log W). Knapsack ist O(n · W) — das W wird als Zahl gezählt, nicht als Bits → 'pseudo'-polynomial. Bei sehr großen W wird's langsam.

F2.Greedy findet IMMER das Optimum, wenn das Problem überhaupt eine Lösung hat.

Antwort: Falsch

Erklärung: FALSCH. Greedy macht lokal beste Entscheidungen → optimal NUR bei Problemen mit Greedy-Auswahl-Eigenschaft (z.B. Münzwechsel mit 1/5/10/25). Bei Münzen {1, 6, 10} und Ziel 12: Greedy=3 Münzen (10+1+1), DP=2 Münzen (6+6). DP ist garantiert optimal.

Typ: Wahr/Falsch

F3.Beim Knapsack-Problem mit DP: was steht in dp[i][c]?

Antwort: Maximaler Wert mit ersten i Items und Kapazität c

Erklärung: dp[i][c] = MAXIMALER WERT, den man mit den ersten i Items und einer Kapazität von c erreichen kann. Rekurrenz: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w_i] + v_i). Erste Option: Item i nicht nehmen. Zweite: nehmen.

F4.Bei welchem Problem ist Memoization (Top-Down) klar BESSER als Tabulation (Bottom-Up)?

Antwort: Wenn nur wenige Teilprobleme tatsächlich gebraucht werden

Erklärung: Memoization berechnet nur Teilprobleme die WIRKLICH gebraucht werden (lazy). Tabulation berechnet alle systematisch. Wenn die meisten Teilprobleme nicht relevant sind, ist Memoization deutlich schneller.

F5.DP braucht zwei Eigenschaften: {{1}} Substruktur und {{2}} Teilprobleme. {{3}} (Top-Down) ist rekursiv mit Caching, {{4}} (Bottom-Up) ist iterativ mit Tabelle. Naive Fibonacci ist {{5}} (Laufzeit-Klasse), mit DP wird daraus O(n).

Lösungen pro Lücke:

{{1}}: optimale / optimal
{{2}}: überlappende / überlappend / ueberlappende
{{3}}: Memoization / memoization
{{4}}: Tabulation / tabulation
{{5}}: exponentiell / O(2^n) / exponential

Erklärung: Standard-Vokabular DP. Voraussetzungen + zwei Stile + Beispiel-Laufzeit-Verbesserung von 2ⁿ auf n.

Typ: Lückentext

F6.Sortiere: Schritte beim Lösen einer DP-Aufgabe.

Richtige Reihenfolge:

Teilprobleme identifizieren
Rekurrenz aufstellen: dp[i] = f(dp[i-1], ...)
Basis-Fälle definieren
Memoization-Tabelle oder iterative Tabulation
Tabelle befüllen (rekursiv oder iterativ)
Antwort aus dp[n] (oder Endpunkt) ablesen

Erklärung: Standard-Klausur-Workflow für DP-Aufgaben. Teilprobleme → Rekurrenz → Basis → Stil wählen → befüllen → Antwort.

Typ: Reihenfolge

Erklärung

Erklärung

Die Idee in einem Satz

Voraussetzungen (Klausur-Pflichtwissen)

Beispiel: Fibonacci

Zwei DP-Stile

Memoization (Top-Down)

Tabulation (Bottom-Up)

Standard-DP-Probleme (klausur-relevant)

1. Rucksack-Problem (0/1 Knapsack)

2. Längste gemeinsame Teilfolge (LCS)

3. Edit-Distanz (Levenshtein)

4. Münzwechsel

5. Längste aufsteigende Teilfolge (LIS)

DP vs. Greedy

Klausur-Faustregeln

Häufige Stolpersteine

DP-Tabellen-Stepper

Wenn du fertig bist: jetzt üben.

Die Idee in einem Satz

Voraussetzungen (Klausur-Pflichtwissen)

Beispiel: Fibonacci

Zwei DP-Stile

Memoization (Top-Down)

Tabulation (Bottom-Up)

Standard-DP-Probleme (klausur-relevant)

1. Rucksack-Problem (0/1 Knapsack)

2. Längste gemeinsame Teilfolge (LCS)

3. Edit-Distanz (Levenshtein)

4. Münzwechsel

5. Längste aufsteigende Teilfolge (LIS)

DP vs. Greedy

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

DP-Tabellen-Stepper

Praxis-Übung

Dynamische Programmierung — Praxis-Übung

Klausur-Quiz