Unique Paths

Q: Wie lautet die Formel für eindeutige Pfade?

Die Antwort ist der Binomialkoeffizient C(m+n-2, m-1) . Jeder Pfad besteht aus m-1 Schritten nach unten und n-1 Schritten nach rechts in beliebiger Reihenfolge. Die Auswahl, welche der m+n-2 Schritte nach unten führen, legt den Pfad fest. Für ein 3 × 4-Raster gilt C(5, 2) = 10.

MittelDynamische Programmierung Mathe und Simulation

+10

Ein Roboter startet in der Zelle oben links eines Gitters mit m Zeilen und n Spalten und muss die Zelle unten rechts erreichen. Bei jedem Schritt bewegt er sich eine Zelle nach rechts oder eine Zelle nach unten. Gib die Anzahl der verschiedenen Wege zurück, die er nehmen kann.

Funktion

uniquePaths(m: integer, n: integer) → integer

minteger: die Anzahl der Zeilen im Raster
ninteger: die Anzahl der Spalten im Raster
Gibt zurückinteger: die Anzahl der verschiedenen Wege von der Zelle oben links zur Zelle unten rechts

Einschränkungen

1 ≤ m, n ≤ 100
Die Antwort beträgt höchstens 2 × 10⁹, daher passt sie in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: m = 3n = 4
Ausgabe: 10
Erklärung: Jeder Pfad macht 2 Schritte nach unten und 3 Schritte nach rechts, insgesamt 5 Schritte. Ein Pfad wird dadurch festgelegt, welche 2 der 5 Schritte nach unten gehen; dafür gibt es 10 Möglichkeiten.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Für ein 100 × 100-Raster hat die Antwort 59 Ziffern. Wie würdest du sie mithilfe der Formel modulo 10^9+7 zurückgeben, wenn die Division durch i nicht mehr funktioniert?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Wege einzeln aufzulisten ist aussichtslos: Ein 17 × 17-Raster hat bereits 601,080,390 davon. Du musst zählen, ohne sie aufzulisten. Die Wege zu einer Zelle sind die Wege zur Zelle darüber plus die Wege zur Zelle links davon. Dadurch wird das Raster zu einer Tabelle, die du in einem Durchgang ausfüllst. Ein Weg ist außerdem nichts anderes als eine Reihenfolge aus Abwärts- und Rechtsschritten, und daraus ergibt sich eine geschlossene Formel.

Jeden Pfad mit Rekursion zählen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Denk an den letzten Schritt des Roboters in die Zelle unten rechts. Er kam entweder von der Zelle darüber nach unten oder von der Zelle links davon nach rechts, aber niemals beides. Daher sind die Wege durch ein m × n-Raster die Wege durch das Raster mit einer Zeile weniger, uniquePaths(m-1, n), plus die Wege durch das Raster mit einer Spalte weniger, uniquePaths(m, n-1).

Die Rekursion endet bei einem Raster mit einer Zeile oder einer Spalte, in dem der Roboter nur geradeaus gehen kann, daher gibt es genau 1 Weg. Jeder Weg endet mit einem der beiden Schritte, also wird jeder Weg genau einmal gezählt und die Summe stimmt.

Das ist langsam, weil jeder Weg in einem Basisfall endet, der 1 zurückgibt, sodass die Anzahl der Aufrufe mindestens so groß wie die Antwort ist. Ein Raster mit 17 × 17 Zellen erfordert mehr als 600 Millionen Aufrufe, und die Tests gehen bis zu Antworten nahe 1.6 × 10^9. Dieselben kleineren Raster werden viele Male berechnet: (m-1, n-1) wird von jedem seiner beiden übergeordneten Raster aus erreicht, und die Wiederholungen vervielfachen sich, je weiter man nach unten geht.

Algorithmus

Wenn m oder n 1 ist, gib 1 zurück: Der einzige Weg ist eine gerade Linie.
Zähle andernfalls die Wege, deren letzter Schritt nach unten führt: uniquePaths(m-1, n).
Zähle die Wege, deren letzter Schritt nach rechts führt: uniquePaths(m, n-1).
Gib ihre Summe zurück.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

Fülle das Raster Zeile für Zeile aus

Idee

Die Rekursion fragt immer wieder nach denselben Zellen, und es gibt nur m × n Zellen. Zähle die Pfade zu jeder Zelle genau einmal, und zwar in einer Reihenfolge, in der die benötigten Zellen immer schon bereit sind.

Zustand: paths[r][c] ist die Anzahl der Pfade von der Zelle oben links zu Zeile r, Spalte c. Rekurrenz: paths[r][c] = paths[r-1][c] + paths[r][c-1], also die Pfade, die von oben ankommen, plus die Pfade, die von links ankommen. Basisfälle: Jede Zelle in der obersten Zeile und in der linken Spalte hat 1 Pfad, eine gerade Linie. Reihenfolge: Zeile für Zeile, von links nach rechts, sodass die Zelle darüber und die Zelle links davon ausgefüllt sind, bevor du sie brauchst.

Für m = 3 und n = 4 lauten die Zeilen 1 1 1 1, dann 1 2 3 4, dann 1 3 6 10, und die Antwort ist die letzte Zelle: 10.

Schau dir nun an, was beim Ausfüllen gelesen wird: nur die Zeile darüber und die Zeile, die gerade ausgefüllt wird. Behalte also nur eine Zeile. Bevor du row[c] aktualisierst, enthält es noch die Anzahl aus der Zeile darüber, und row[c-1] enthält bereits die neue Anzahl links davon. Daher bildet row[c] += row[c-1] die gesamte Rekurrenz. Die Laufzeit bleibt O(m × n), und der Speicherbedarf sinkt von O(m × n) auf O(n).

Algorithmus

Erstelle row mit n Einträgen, die alle 1 sind: die oberste Zeile.
Wiederhole dies m-1 Mal, einmal für jede Zeile unterhalb der obersten.
Addiere in jeder Zeile für c von 1 bis n-1 row[c-1] zu row[c]. row[0] bleibt 1: Das ist die linke Spalte.
Gib row[n-1] zurück.

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

Anzahl der Züge mit einem Binomialkoeffizienten

Idee

Jeder Pfad macht genau m-1 Schritte nach unten und n-1 Schritte nach rechts, insgesamt also m+n-2 Schritte, in beliebiger Reihenfolge. Jede Reihenfolge ergibt einen gültigen Pfad: Der Roboter macht nie mehr als m-1 Schritte nach unten oder n-1 Schritte nach rechts und verlässt daher nie das Raster. Ein Pfad entspricht also der Auswahl, welche m-1 der m+n-2 Schritte nach unten führen, und die Antwort ist der Binomialkoeffizient C(m+n-2, m-1).

Die Tabelle aus dem letzten Ansatz ist Pascalsches Dreieck, auf die Seite gedreht, weshalb beide übereinstimmen. Um den Koeffizienten ohne riesige Fakultäten zu berechnen, baue ihn Faktor für Faktor auf. Mit N = m+n-2 und k = min(m, n)-1 multiplizierst du mit N-k+i und teilst dann durch i, für i von 1 bis k. Nach Schritt i ist der laufende Wert C(N-k+i, i), eine ganze Zahl, sodass jede Division exakt aufgeht.

Für m = 3 und n = 4: N = 5, k = 2, und der Wert steigt von 1 × 4 / 1 = 4 auf 4 × 5 / 2 = 10. Wenn du die kürzere Seite wählst, bleibt die Schleife bei höchstens 99 Schritten. Das Produkt vor der letzten Division ist das k-Fache der Antwort. Bei einem Raster mit 17 × 17 Feldern ergibt das 16 × 601,080,390, also etwa 9.6 × 10^9, was außerhalb des 32-Bit-Bereichs liegt. Speichere den Wert daher in einer 64-Bit-Ganzzahl.

Algorithmus

Setze N = m+n-2, die Anzahl der Züge, und k = min(m, n)-1.
Beginne mit einem 64-Bit-Zähler bei 1.
Multipliziere den Zähler für i von 1 bis k mit N-k+i und teile ihn anschließend durch i.
Gib den Zähler zurück.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

Stolperfallen und Grenzfälle

Die Zählung ist kurz, daher verstecken sich die Fehler an den Rändern des Gitters und in der Größe der Zahlen.

Die Berechnung von (m+n-2)! und die Division durch die beiden anderen Fakultäten führen lange vor dem Ergebnis zu einem Überlauf: 21! liegt bereits außerhalb des 64-Bit-Bereichs, und m+n-2 erreicht in einem 100 × 7-Gitter den Wert 105.
Wenn du vor dem Multiplizieren dividierst, wie bei count / i * (N-k+i), wird abgerundet, denn count ist nicht immer ein Vielfaches von i. Multipliziere zuerst: Das Produkt ist immer exakt teilbar.
Das Produkt count × (N-k+i) kann 2^31 überschreiten, auch wenn das Ergebnis dies nicht tut. Speichere es in einer 64-Bit-Ganzzahl.
Wenn du die oberste Zeile oder die linke Spalte auf 0 statt auf 1 setzt, wird jede Zelle zu 0. Ein Gitter mit einer Zeile oder einer Spalte hat genau 1 Pfad.
Das Vertauschen von Zeilen und Spalten ändert das Ergebnis nicht, da C(m+n-2, m-1) = C(m+n-2, n-1).

Häufige Fragen4

Wie lautet die Formel für eindeutige Pfade?

Die Antwort ist der Binomialkoeffizient C(m+n-2, m-1). Jeder Pfad besteht aus m-1 Schritten nach unten und n-1 Schritten nach rechts in beliebiger Reihenfolge. Die Auswahl, welche der m+n-2 Schritte nach unten führen, legt den Pfad fest. Für ein 3 × 4-Raster gilt C(5, 2) = 10.

Wie hoch ist die Zeitkomplexität von Unique Paths?

Die Tabelle der dynamischen Programmierung benötigt O(m × n) Zeit und O(n) Speicherplatz, wenn du eine Zeile beibehältst. Die Binomialformel benötigt O(min(m, n)) Zeit und O(1) Speicherplatz. Eine einfache Rekursion führt mindestens so viele Aufrufe aus, wie es Pfade gibt, was exponentiell in m + n ist.

Wie löst man Unique Paths, wenn einige Zellen blockiert sind?

Verwende dieselbe Tabelle und setze die Anzahl für ein blockiertes Feld auf 0, damit kein Pfad hindurchführt. Die oberste Zeile und die linke Spalte bestehen nicht mehr nur aus 1en: Jedes Feld nach einem blockierten Feld in der obersten Zeile hat 0 Pfade. Die Formel funktioniert nicht mehr, weil sie davon ausgeht, dass jede Reihenfolge von Bewegungen erlaubt ist.

Warum entspricht die Tabelle der eindeutigen Pfade dem Pascalschen Dreieck?

Jede Zelle ist die Summe der Zelle darüber und der Zelle links davon. Das ist die Regel, nach der das Pascalsche Dreieck entsteht, wenn man es entlang seiner Diagonalen liest. Die Zelle in Zeile r und Spalte c enthält C(r+c, r), daher enthält die Zelle unten rechts C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

m = 3
n = 4

Erwartet

Unique Paths

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jeden Pfad mit Rekursion zählen

Fülle das Raster Zeile für Zeile aus

Anzahl der Züge mit einem Binomialkoeffizienten

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben