Was ist dynamische Programmierung in einfachen Worten?
Stellen Sie sich vor, Sie berechnen die Fakultät der Zahl 5.
Dazu benötigen Sie: 5 × 4 × 3 × 2 × 1. Und jetzt werden Sie gebeten, die Fakultät von 6 zu berechnen. Es ist dumm, alles noch einmal zu zählen, oder? Sie wissen bereits, dass 5! = 120, multiplizieren Sie einfach mit 6.
Dynamische Programmierung (DP) - das ist genau der gleiche Ansatz: Wir lösen ein komplexes Problem, indem wir es in Teilaufgaben zerlegen, und Ergebnisse speichern, um dasselbe nicht zweimal zu zählen.
Die Hauptmerkmale der Aufgaben bei der Auftragsvergabe:
🎯 Optimale Unterkonstruktion
Die Lösung eines großen Problems besteht aus Lösungen kleinerer Teilprobleme
🔄 Überlappende Teilaufgaben
Einige Aufgaben wiederholen sich
⚡ Es ist notwendig, das Optimum zu finden
Maximum, Minimum oder Anzahl der Methoden
Zwei Ansätze für DP: Memo und Tab
1. Auswendiglernen (von oben nach unten)
Dies ist Rekursion + Zwischenspeicherung der Ergebnisse. Wir beginnen mit einer großen Aufgabe und gehen zu den Grundfällen über.
def fibonacci_memo(n, memo={}):
# Grundfälle
if n <= 1:
return n
# Wir überprüfen den Cache
if n in memo:
return memo[n]
# Berechnen und speichern
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(50)) # Sofort!Wann zu verwenden: wenn die Logik der Aufgabe durch Rekursion intuitiv verständlich ist.
2. Tabulation (von unten nach oben)
Wir erstellen eine Lösungstabelle von den Basisfällen bis zur endgültigen Antwort. Keine Rekursion!
def fibonacci_table(n):
if n <= 1:
return n
# Erstellen Sie eine Tabelle
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Von unten nach oben ausfüllen
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci_table(50))Wann zu verwenden: wenn maximale Leistung und Speicherkontrolle erforderlich sind.
Klassische Aufgaben der DV, die man 2026 kennen muss
Aufgabe 1: Fibonacci-Zahlen
Schwierigkeit ohne DP: O(2ⁿ) — exponentiell!
Schwierigkeit mit DP: O(n) - linear!
Wir haben die Lösung bereits oben gesehen. Dies ist eine ideale Aufgabe für den Anfang.
Aufgabe 2: Rucksackproblem (Knapsack Problem)
Sie sind ein Räuber mit einem Rucksack mit einem Fassungsvermögen von W. Es gibt Gegenstände mit Gewicht und Wert. Wie kann man den maximalen Wert nehmen?
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = maximaler Wert für i Artikel und Kapazität w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
# Wir nehmen den Gegenstand nicht
dp[i][w] = dp[i-1][w]
# Wir nehmen den Gegenstand, wenn er hineinpasst
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
weights = [1, 2, 3, 5]
values = [10, 5, 15, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 32Anwendung in der Realität: Ressourcenverteilung, Budgetplanung, Optimierung der Serverauslastung.
Aufgabe 3: Längste gemeinsame Teilfolge (LCS)
Finden Sie die längste gemeinsame Teilfolge von zwei Zeilen. Basis für git diff!
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs("ABCDGH", "AEDFHR")) # 3 (ADH)Anwendung: Versionskontrollsysteme, Plagiatsprüfung, Bioinformatik (DNA-Vergleich).
Aufgabe 4: Münzwechsel
Es gibt Münzen verschiedener Stückelungen. Auf wie viele Arten kann man den Betrag sammeln?
def coin_change(coins, amount):
# dp[i] = Mindestanzahl von Münzen für den Betrag i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Für den Betrag 0 benötigen Sie 0 Münzen
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
coins = [1, 2, 5]
amount = 11print(coin_change(coins, amount)) # 3 (5+5+1)Anwendung: Fintech-Anwendungen, Kassensysteme, Transaktionsoptimierung.
Aufgabe 5: Edit Distance (Levenshtein-Abstand)
Die Mindestanzahl von Operationen, um eine Zeile in eine andere umzuwandeln.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialisierung
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Ausfüllen der Tabelle
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # Entfernung
dp[i][j-1], # Einfügen
dp[i-1][j-1] # Ersatz
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3Anwendung: Korrektur von Tippfehlern, Suchmaschinen, Autovervollständigung.
Schritt-für-Schritt-Methode zur Lösung von Problemen bei der DP
Schritt 1: Finden Sie eine rekursive Lösung
Lösen Sie das Problem zunächst einfach rekursiv, ohne über Optimierung nachzudenken.
# Nicht optimierte Versiondef fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Schritt 2: Memoisierung hinzufügen
Fügen Sie ein Wörterbuch hinzu, um die Ergebnisse zu speichern.
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Schritt 3: Konvertieren Sie in Tab (optional)
Übersetzen Sie in einen iterativen Ansatz mit einem Array.
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Schritt 4: Speicher optimieren
Oft kann man O(1) Speicher anstelle von O(n) verwenden.
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1Wichtige Muster der Direktzahlungen im Jahr 2026
1D DP
Eindimensionales Array
Fibonacci-Zahlen
Climbing Stairs
House Robber
2D-DP
Zweidimensionales Array
Longest Common Subsequence
Edit Distance
Knapsack Problem
DP auf Zeilen
Arbeit mit Text
Palindrome Subsequences
String Matching
Wildcard Matching
DP auf Bäumen
Baumstrukturen
Binary Tree Maximum Path Sum
Diameter of Binary Tree
DP auf Grafen
Graphenalgorithmen
Shortest Path (Bellman-Ford)
Traveling Salesman Problem
Typische Anfängerfehler
Fehler 1: Sie vergessen die grundlegenden Fälle
def fib(n):
return fib(n-1) + fib(n-2)
# Endlose Rekursion!Richtig
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Fehler 2: Falsche Tabellengröße
dp = [0] * n
# Wenn Sie Indizes 0..n benötigen,
# Größe n+1 benötigt!Richtig
dp = [0] * (n + 1)Fehler 3: Grenzen werden nicht überprüft
if dp[i-1]:
# Was ist, wenn i = 0?Richtig
if i > 0 and dp[i-1]:Praktische Tipps für Vorstellungsgespräche.
Zeichnen Sie eine Tabelle auf Papier - Visualisierung hilft, Abhängigkeiten zu finden
Beginnen Sie mit kleinen Beispielen — fib(0), fib(1), fib(2)...
Suchen Sie nach der Rekursionsformel — Wie hängt dp[i] von den vorherigen Werten ab?
Sprechen Sie die Logik laut aus - dies zeigt den Verlauf Ihrer Gedanken
Scheuen Sie sich nicht, zunächst eine suboptimale Lösung zu schreiben - dann kann es verbessert werden
JavaScript-Version für Webentwickler.
Viele Anfänger arbeiten mit JavaScript, daher hier ein Beispiel für JS:
// Speicherfunktion fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulationfunction fibTable(n) {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Optimierte Version (O(1) Speicher)function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(fibOptimized(50)); // 12586269025Schlussfolgerung.
Dynamische Programmierung ist keine Magie, sondern ein logischer Ansatz zur Problemlösung. Wichtigste Punkte:
Aufteilen in Unteraufgaben — Finden Sie das Wiederholungsmuster
Speichern Sie die Ergebnisse — nicht doppelt zählen
Beginnen Sie mit der Rekursion — dann optimieren
Trainieren Sie regelmäßig - DP erfordert Übung
Nachdem Sie die dynamische Programmierung gemeistert haben, werden Sie:
✅ Bestehen Sie die meisten technischen Vorstellungsgespräche
✅ Sie können echte Aufgaben in der Produktion optimieren
✅ Sie verstehen, wie viele Bibliotheken und Frameworks funktionieren
✅ Lernen Sie, algorithmisch zu denken
Denken Sie daran: Jeder Algorithmus schien einmal selbst den besten Entwicklern kompliziert zu sein. Hauptsache Übung und Geduld.
Lernen Sie dynamische Programmierung und viele andere wichtige Themen in Kodik – einer Bildungsplattform mit praktischen Kursen für Entwickler. Wir erstellen Inhalte, die bei Vorstellungsgesprächen und bei der Arbeit wirklich helfen!
📱 Und wir haben auch eine coole Telegram-Kanal mit einer freundlichen Community, wo:
Wir analysieren die Aufgaben aus den Interviews
Wir teilen nützliche Artikel
Wir helfen uns gegenseitig zu wachsen
Wir diskutieren die neuesten Entwicklungstrends
Zu Kodik gehen Telegram beitreten
Schließe dich einer Community von Entwickler:innen an, die gemeinsam wachsen! 💪