Dynamische Programmierung: Ein Anfänger-Leitfaden für Informatikolympiaden

Wer zum ersten Mal auf den Begriff Dynamische Programmierung trifft, erwartet vielleicht etwas mit modernen Programmiersprachen oder Software-Architekturen. Tatsächlich handelt es sich um eine der elegantesten algorithmischen Techniken überhaupt – und gleichzeitig um eine der häufigsten Hürden bei der Vorbereitung auf die Informatik-Olympiade. Wer DP einmal wirklich verstanden hat, sieht Probleme auf eine völlig neue Weise.

Was ist Dynamische Programmierung?

Der Begriff wurde in den 1940er Jahren vom Mathematiker Richard Bellman geprägt. Die Grundidee ist simpel: Ein komplexes Problem wird in kleinere Teilprobleme zerlegt, deren Ergebnisse gespeichert werden – damit man sie nicht mehrfach berechnen muss.

Wie Wikipedia zur Dynamischen Programmierung treffend zusammenfasst: Einmal berechnete Teilergebnisse werden in einer Tabelle gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen.

Damit DP anwendbar ist, muss ein Problem zwei Eigenschaften besitzen:

• Überlappende Teilprobleme (overlapping subproblems): Dieselben Teilprobleme tauchen mehrfach auf.
• Optimale Substruktur (optimal substructure): Eine optimale Lösung des Gesamtproblems lässt sich aus optimalen Lösungen der Teilprobleme zusammensetzen.

Zwei Ansätze: Top-Down vs. Bottom-Up

Es gibt zwei klassische Wege, DP umzusetzen.

Top-Down mit Memoization

Beim Top-Down-Ansatz schreibt man zunächst eine normale Rekursion – und ergänzt dann ein Speicherobjekt (meist ein Array oder ein Dictionary), das bereits berechnete Ergebnisse aufbewahrt. Bevor eine Funktion das Ergebnis neu berechnet, schaut sie nach, ob es schon gespeichert ist.

Bottom-Up mit Tabellierung

Beim Bottom-Up-Ansatz löst man die kleinsten Teilprobleme zuerst und baut die Lösung iterativ auf. Das Ergebnis wird in einer Tabelle (oft ein Array) aufgebaut, bis man beim eigentlichen Problem angekommen ist. Dieser Ansatz vermeidet Rekursion gänzlich und ist in der Praxis oft schneller.

Welcher Ansatz besser ist, hängt vom Problem ab. Bei Olympiaden sind beide gebräuchlich.

Beispiel 1: Die Fibonacci-Folge

Die Fibonacci-Folge ist das klassische Einstiegsbeispiel für DP – nicht weil sie besonders schwer wäre, sondern weil sie das Problem mit naiver Rekursion so deutlich zeigt.

Die naive Rekursion fib(n) = fib(n-1) + fib(n-2) hat exponentielle Laufzeit O(2ⁿ). Für fib(50) würde ein normaler Rechner schon ins Straucheln geraten.

Mit Memoization sieht das so aus (Pseudocode):

memo = {}

funktion fib(n):
    wenn n <= 1: gib n zurück
    wenn n in memo: gib memo[n] zurück
    memo[n] = fib(n-1) + fib(n-2)
    gib memo[n] zurück

Alternativ Bottom-Up:

dp[0] = 0
dp[1] = 1
für i von 2 bis n:
    dp[i] = dp[i-1] + dp[i-2]
gib dp[n] zurück

Die Laufzeit sinkt auf O(n) – ein drastischer Unterschied. Eine anschauliche Erklärung mit konkreten Zahlen bietet auch Serlo zu Fibonacci und Dynamischer Programmierung.

Beispiel 2: Das Rucksackproblem

Das Rucksackproblem ist ein Klassiker der Kombinatorik und ein festes Element vieler Informatik-Olympiaden. Die Aufgabenstellung: Gegeben sind n Gegenstände mit je einem Gewicht und einem Wert. Ein Rucksack trägt maximal das Gewicht W. Welche Auswahl von Gegenständen maximiert den Gesamtwert, ohne das Gewichtslimit zu überschreiten?

Die DP-Lösung

Man definiert dp[i][w] als den maximalen Wert, den man mit den ersten i Gegenständen und maximalem Gewicht w erzielen kann.

für i von 1 bis n:
    für w von 0 bis W:
        dp[i][w] = dp[i-1][w]  // Gegenstand i nicht einpacken
        wenn gewicht[i] <= w:
            dp[i][w] = max(dp[i][w], dp[i-1][w - gewicht[i]] + wert[i])

Das Ergebnis steht in dp[n][W]. Die Laufzeit beträgt O(n · W) – für die meisten Olympiade-Aufgaben vollkommen ausreichend.

Das Schöne an diesem Ansatz: Man muss nicht alle möglichen Kombinationen durchprobieren (das wären 2ⁿ). Stattdessen baut man die Lösung systematisch auf.

Häufige DP-Muster bei Olympiaden

Mit Fibonacci und Rucksack ist der Einstieg gemacht. In echten Olympiade-Aufgaben begegnen einem weitere Standardmuster, die es lohnt zu kennen:

• Längste gemeinsame Teilsequenz (LCS): Zwei Strings, maximale gemeinsame Subsequenz finden.
• Längste aufsteigende Teilfolge (LIS): In einer Folge die längste streng aufsteigende Subsequenz bestimmen.
• Münzwechsel (Coin Change): Mit gegebenen Münzwerten einen Betrag mit möglichst wenigen Münzen darstellen.
• Matrixpfade: Kürzeste oder billigste Pfade durch ein Gitter finden.
• Intervall-DP: Teilprobleme sind Intervalle einer Folge – typisch bei Klammerungsproblemen oder dem optimalen Matrixkettenprodukt.

Wie erkenne ich ein DP-Problem?

Eine einfache Faustregel: Wenn die Aufgabe nach einem Minimum, Maximum, einer Anzahl von Möglichkeiten oder der Existenz einer Lösung fragt, und sich dabei Teilprobleme wiederholen, ist DP sehr wahrscheinlich der richtige Ansatz.

Tipps für die Olympiade-Vorbereitung

Anfangen mit dem Zustand. Der wichtigste Schritt bei DP ist die Frage: Was genau speichere ich? Die Definition des Zustands dp[i] oder dp[i][j] entscheidet über alles.

Übergänge aufschreiben. Bevor man code schreibt, lohnt es sich, die Übergänge mathematisch zu formulieren. Was hängt dp[i] von früheren Zuständen ab?

Kleine Beispiele durchrechnen. Für Olympiaden gilt: immer erst an Hand kleiner Eingaben per Hand rechnen. Das deckt Fehler in der Zustandsdefinition früh auf.

Aufgaben üben. Die Swiss Olympiad in Informatics bietet hervorragende DP-Einstiegsaufgaben mit Erklärungen – ein empfehlenswerter Startpunkt neben den deutschen Bundeswettbewerben.

Dynamische Programmierung ist keine Magie – sie ist eine Denkweise. Wer lernt, Probleme in ihre Teilprobleme zu zerlegen und Zwischenergebnisse konsequent zu nutzen, wird nicht nur bei der Informatik-Olympiade erfolgreicher sein. DP-Algorithmen sind das Fundament unzähliger realer Anwendungen: von Navigationssystemen über Gensequenzierung bis hin zu Sprachmodellen. Der Einstieg lohnt sich auf ganzer Linie.