Eindeutige Pfade und minimale Pfadsumme in Rastern
Füllen Sie eine 2D-DP-Tabelle für eindeutige Pfade mit und ohne Hindernisse und passen Sie sie anschließend an, um die Summe der Werte entlang eines Pfades zu minimieren.
Eindeutige Pfade und minimale Pfadsumme in Rastern ist eine kostenlose DSA 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Unique Paths auf einem Gitter
Unique Paths (LeetCode 62) stellt die Frage: Wie viele verschiedene Pfade führen in einem m×n-Gitter von der oberen linken Ecke zur unteren rechten Ecke, wenn Sie sich nur nach rechts oder nach unten bewegen dürfen? Für ein 3×7-Gitter lautet die Antwort 28. Die entscheidende Erkenntnis ist, dass jeder Pfad zur Zelle (i,j) entweder von (i-1,j) (oben) oder von (i,j-1) (links) kommen muss. Daraus ergibt sich unmittelbar eine zweidimensionale DP-Formulierung.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 22D-DP-Tabelle für Unique Paths
Definieren Sie dp[i][j] als die Anzahl der Pfade zur Zelle (i,j). Die erste Zeile und die erste Spalte bestehen vollständig aus 1en, da jede Zelle in der obersten Zeile oder der äußersten linken Spalte nur auf eine Weise erreicht werden kann. Für die übrigen Zellen gilt: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Füllen Sie die Tabelle zeilenweise aus; die Antwort ist dp[m-1][n-1]. Zeitkomplexität: O(m×n), Speicherbedarf: O(m×n), reduzierbar auf O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)Speicheroptimierung auf O(n)
Da dp[i][j] nur von der aktuellen und der vorherigen Zeile abhängt, können Sie die vollständige 2D-Tabelle durch ein einzelnes eindimensionales Array ersetzen. Initialisieren Sie alle Werte mit 1 und aktualisieren Sie das Array anschließend für jede Zeile direkt: dp[j] += dp[j-1]. Nach der Verarbeitung der Zeile i enthält dp[j] den Wert, der in der 2D-Tabelle dp[i][j] entsprach. Dies ist ein häufig verwendetes Optimierungsmuster für 2D-DP-Probleme.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Unique Paths II: Hindernisse
Unique Paths II (LeetCode 63) fügt dem Gitter Hindernisse hinzu (mit 1 markierte Zellen). Jeder Pfad durch ein Hindernis ist ungültig, daher gilt dp[i][j] = 0, wenn obstacle[i][j] == 1. Andernfalls bleibt die Rekurrenz unverändert: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Ist der Start oder das Ziel blockiert, lautet das Ergebnis sofort 0. Initialisieren Sie die Anfangsfälle sorgfältig — sobald in der ersten Zeile oder Spalte eine 1 auftritt, sind alle nachfolgenden Zellen in dieser Zeile oder Spalte 0.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Problem der minimalen Pfadsumme
Minimum Path Sum (LeetCode 64) stellt die Frage: Gegeben sei ein m×n-Gitter mit nichtnegativen ganzen Zahlen. Finden Sie den Pfad von oben links nach unten rechts, dessen Summe aller Zahlen entlang des Pfades minimal ist (Bewegung nur nach rechts oder unten). Im Beispiel [[1,3,1],[1,5,1],[4,2,1]] ergibt der Pfad 1→3→1→1→1 die Summe 7. Der DP-Zustand ist derselbe wie bei Unique Paths, aber die Rekurrenz verwendet nun das Minimum statt der Addition.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)Implementierung der DP für die minimale Pfadsumme
Definieren Sie dp[i][j] als die minimalen Kosten, um die Zelle (i,j) zu erreichen. Anfangsfall: dp[0][0] = grid[0][0]. Erste Zeile: dp[0][j] = dp[0][j-1] + grid[0][j] (der einzige Weg führt von links). Erste Spalte: dp[i][0] = dp[i-1][0] + grid[i][0] (der einzige Weg führt von oben). Allgemein gilt: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Dies ist eine direkte Umsetzung des Optimalitätsprinzips.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7Minimale Pfadsumme direkt im Gitter
Wenn Sie das Eingabegitter verändern dürfen, können Sie es direkt aktualisieren und so die Zuweisung einer separaten DP-Tabelle vermeiden. Dadurch sinkt der zusätzliche Speicherbedarf (über die Eingabe hinaus) auf O(1). In Interviews wird manchmal nach dieser Optimierung gefragt — klären Sie, ob das Ändern der Eingabe erlaubt ist, bevor Sie dies tun. Falls nicht, bietet der Trick mit dem rollierenden 1D-Array O(n) Speicher, ohne die Eingabe zu verändern.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Minimale Pfadsumme im Dreieck
Triangle (LeetCode 120) fragt nach der minimalen Pfadsumme von oben nach unten in einem Dreiecksarray, wobei jeder Schritt zu einer benachbarten Zahl in der darunterliegenden Zeile führt. Bottom-up-DP ist am übersichtlichsten: Beginnen Sie in der vorletzten Zeile und addieren Sie für jede Zelle das Minimum der beiden direkt darunterliegenden Zellen. So müssen Sie keine Startindizes verfolgen, und die Antwort wird auf natürliche Weise bis zur Spitze weitergereicht.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)Gitter-DP im Dungeon
Dungeon Game (LeetCode 174) fragt nach der minimalen anfänglichen Gesundheit, die erforderlich ist, um eine Prinzessin in der unteren rechten Ecke eines Gitters mit negativen (Schaden verursachenden) und positiven (heilenden) Zellen zu retten. Sie müssen sich nach rechts oder unten bewegen. Der Trick besteht darin, die DP-Tabelle rückwärts zu füllen (von unten rechts nach oben links) und für jede Zelle die mindestens benötigte Gesundheit zu berechnen. Für jede Zelle gilt: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Die Gesundheit muss stets mindestens 1 betragen.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Vergleich von Gitter-DP-Problemen
Gitter-DP-Probleme haben dieselbe Struktur, unterscheiden sich aber in der Füllrichtung und der Übergangsoperation: Unique Paths verwendet Addition (zählt alle Möglichkeiten). Min Path Sum verwendet das Minimum (optimiert). Dungeon Game füllt die Tabelle rückwärts (benötigte Gesundheit ausgehend von den späteren Feldern). Wenn Sie ein neues Gitter-DP-Problem angehen, fragen Sie sich: (1) Was stellt jede Zelle dar? (2) In welche Richtung fülle ich die Tabelle? (3) Welche Operation kombiniert die Nachbarn? Die Antworten auf diese drei Fragen zeigen die vollständige Lösung auf.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Zusammenfassung der Komplexität bei Gitter-DP
Alle hier behandelten Gitter-DP-Probleme benötigen O(m×n) Zeit. Der Speicherbedarf reicht von O(m×n) für eine vollständige Tabelle über O(n) mit einem rollierenden 1D-Array bis zu O(1) zusätzlichem Speicher, wenn das Gitter direkt verändert werden kann. Erwähnen Sie in Interviews die Speicheroptimierung auf O(n), nachdem Sie die Lösung mit O(m×n) vorgestellt haben — das zeigt, dass Sie sich der Abwägungen bewusst sind. Prüfen Sie bei allen Problemen außerdem, ob eine Greedy-Abkürzung existiert (wie die mathematische Formel für Unique Paths).
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Unique Paths füllt eine 2D-Tabelle mit dp[i][j] = dp[i-1][j] + dp[i][j-1] und kann mithilfe der Kombinatorik in O(1) berechnet werden, Min Path Sum verwendet dieselbe Struktur, ersetzt aber die Addition durch min, um die optimalen Pfadkosten zu bestimmen, und alle Gitter-DP-Probleme folgen dem Muster, einen Zustand pro Zelle zu definieren und einen Übergangsoperator (sum, min, max) auszuwählen. Als Nächstes untersuchen wir die Longest Common Subsequence mithilfe von 2D-DP auf zwei Sequenzen.
Häufig gestellte Fragen
Ist die Lektion „Eindeutige Pfade und minimale Pfadsumme in Rastern“ kostenlos?
Ja — der vollständige Text von „Eindeutige Pfade und minimale Pfadsumme in Rastern“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Eindeutige Pfade und minimale Pfadsumme in Rastern“?
Füllen Sie eine 2D-DP-Tabelle für eindeutige Pfade mit und ohne Hindernisse und passen Sie sie anschließend an, um die Summe der Werte entlang eines Pfades zu minimieren. Du übst DSA 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA 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 „Eindeutige Pfade und minimale Pfadsumme in Rastern“?
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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA 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
- Eindeutige Pfade und minimale Pfadsumme in Rastern
- Längste gemeinsame Teilsequenz
- Editierdistanz (Levenshtein)
- Speicheroptimierung für 2D-DP