Minimale Pfadsumme mit Hindernissen
Übertragen Sie die günstigsten Kosten über die Zellen
Minimale Pfadsumme mit Hindernissen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Von Zählen zu Kosten
Nun enthält jede Zelle einen Wert, und Sie möchten den günstigsten Weg zur Ecke finden. Das Ziel verschiebt sich vom Zählen der Pfade zum Minimieren der Kosten.
Zustand definieren
Sei dp[i][j] die geringste Gesamtsumme, mit der die Zelle (i, j) erreicht werden kann. Dasselbe Gitter, dieselben Bewegungen, aber wir verfolgen Summen statt Anzahlen.
Der Übergang
Sie wählen den günstigeren der beiden eingehenden Nachbarn und addieren anschließend die aktuelle Zelle. Diese min-Auswahl bildet den Kern der Rekurrenz.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Hindernisse markieren
Ein Hindernis ist eine Zelle, auf der Sie nicht stehen können. Geben Sie ihr die Kosten unendlich, damit kein Weg durch sie jemals das Minimum sein kann.
INF = float('inf')Sauber blockieren
Wenn das Gitter eine Zelle als blockiert markiert, setzen Sie einfach ihr dp auf unendlich und fahren fort. Der min-Schritt umgeht sie automatisch.
if blocked(i, j):
dp[i][j] = INF
continueStart absichern
Wenn die Startzelle selbst blockiert ist, gibt es überhaupt keinen Pfad. Prüfen Sie das zuerst, damit Sie keine falschen Kosten zurückgeben.
Erste Zelle initialisieren
Vom Start führen keine Nachbarn dorthin, daher entsprechen seine Kosten einfach seinem eigenen Wert. Setzen Sie dp[0][0], bevor die Schleifen beginnen.
dp[0][0] = grid[0][0]Ränder behandeln
In der obersten Zeile geht der Weg nur von links weiter, in der linken Spalte nur von oben. Behandeln Sie diese Ränder, damit Sie nie außerhalb des Gitters lesen.
Unendlich breitet sich aus
Wenn Sie zu unendlich etwas addieren, bleibt das Ergebnis unendlich. Daher behält eine vollständig abgeschnittene Zelle ihre INF-Kosten. Unerreichbare Zellen machen sich automatisch bemerkbar.
Ergebnis ablesen
Die minimalen Kosten stehen in der Zelle unten rechts. Ist dieser Wert weiterhin unendlich, gibt es überhaupt keinen gültigen Pfad.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Wann Greedy hier scheitert
Wenn Sie immer zum kleineren Nachbarn gehen, können Sie in eine Sackgasse geraten. Nur vollständige DP garantiert den global günstigsten Pfad, nicht ein gieriger Blick auf den nächsten Schritt.
Schnelltest
Wie sorgen Sie dafür, dass die Pfad-DP eine blockierte Zelle vermeidet, ohne jeden Nachbarn einzeln mit einer Sonderbehandlung zu versehen?
Zusammenfassung: Minimaler Pfad mit Hindernissen
Wählen Sie den günstigeren Nachbarn, addieren Sie den Zellwert, setzen Sie blockierte Zellen auf unendlich und lesen Sie die Ecke aus. INF dort bedeutet kein Pfad. 🧱
Häufig gestellte Fragen
Ist die Lektion „Minimale Pfadsumme mit Hindernissen“ kostenlos?
Ja — der vollständige Text von „Minimale Pfadsumme mit Hindernissen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Minimale Pfadsumme mit Hindernissen“?
Übertragen Sie die günstigsten Kosten über die Zellen Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 2 von 4.
Wie lange dauert die Lektion „Minimale Pfadsumme mit Hindernissen“?
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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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
- Pfade in einem Raster zählen
- Minimale Pfadsumme mit Hindernissen
- Längste gemeinsame Teilfolge
- Editierdistanz Schritt für Schritt