Pfade in einem Raster zählen
Summieren Sie Pfade von Ecke zu Ecke
Pfade in einem Raster zählen ist eine kostenlose Coding 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das klassische Gitterproblem
Sie beginnen oben links in einem Gitter und möchten nach unten rechts gelangen. Jeder Schritt führt nach rechts oder nach unten. Wie viele verschiedene Pfade gibt es?
Warum DP passt
Jede Zelle kann von der Zelle darüber oder von der Zelle links erreicht werden. Diese Überschneidung ist genau der Grund, warum es sich um ein DP-Problem handelt.
Zustand definieren
Sei dp[i][j] die Anzahl der Möglichkeiten, die Zelle (i, j) vom Start aus zu erreichen. Den Zustand klar zu benennen, ist bereits die halbe Arbeit.
Der Übergang
Sie kommen nur von oben oder von links an, daher ist die Anzahl ihre Summe. Dieser Übergang treibt die gesamte Tabelle an.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Der Basisfall
Die Startzelle kann auf genau eine Weise erreicht werden: indem Sie nichts tun. Daher ist dp[0][0] gleich 1, bevor Sie den Rest ausfüllen.
dp[0][0] = 1An den Rändern gibt es einen Pfad
Zellen in der obersten Zeile oder der linken Spalte haben genau einen geraden Weg. Ihre Anzahl ist immer 1, da jeweils ein Nachbar außerhalb des Gitters liegt.
Tabelle aufbauen
Erstellen Sie eine mit Nullen gefüllte Tabelle der Größe m by n. Wenn Sie die Größe von Anfang an festlegen, bleiben Ihre Indizes übersichtlich und Überraschungen aus.
dp = [[0] * n for _ in range(m)]In Lesereihenfolge ausfüllen
Durchlaufen Sie zuerst die Zeilen und dann die Spalten, von oben nach unten und von links nach rechts. Diese Reihenfolge stellt sicher, dass beide Nachbarn bereitstehen, bevor Sie sie verwenden.
for i in range(m):
for j in range(n):
...Die Antwortzelle
Nach dem Ausfüllen steht die Anzahl der Pfade in der letzten Zelle. Die Antwort ist dp[m-1][n-1], also die Ecke unten rechts.
answer = dp[m-1][n-1]Speicher mit einer Zeile sparen
Jede Zeile benötigt nur die darüberliegende Zeile. Daher können Sie eine einzige Zeile verwenden und sie direkt aktualisieren. Dadurch sinkt der Speicherbedarf auf O(n).
row[j] += row[j-1]Die mathematische Abkürzung
Ohne Hindernisse ist die Antwort ein Binomialkoeffizient: Wählen Sie aus, welche der insgesamt ausgeführten Schritte nach unten führen. Sobald Hindernisse auftreten, ist DP weiterhin die bessere Wahl.
Schnelltest
Sie füllen dp[i][j] für eine freie innere Zelle aus. Welche Formel ist richtig?
Zusammenfassung: Pfade zählen
Definieren Sie dp als die Anzahl der Pfade zu einer Zelle, setzen Sie dp[0][0] auf 1 und addieren Sie die Zelle darüber und die Zelle links. Die Ecke enthält Ihre Antwort. 🧭
Häufig gestellte Fragen
Ist die Lektion „Pfade in einem Raster zählen“ kostenlos?
Ja — der vollständige Text von „Pfade in einem Raster zählen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Pfade in einem Raster zählen“?
Summieren Sie Pfade von Ecke zu Ecke Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 „Pfade in einem Raster zählen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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
- Pfade in einem Raster zählen
- Minimale Pfadsumme mit Hindernissen
- Längste gemeinsame Teilfolge
- Editierdistanz Schritt für Schritt