Pascal's Triangle

Q: Wie hoch ist die Zeitkomplexität beim Erzeugen des Pascalschen Dreiecks?

Das Erstellen jeder Zeile aus der darüberliegenden benötigt für n Zeilen O(n²) Zeit, weil das Dreieck etwa n²/2 Einträge hat und jeder davon durch eine einzelne Addition berechnet wird. Das ist optimal, da du jeden Eintrag der Ausgabe schreiben musst. Abgesehen von der Ausgabe benötigt es O(1) zusätzlichen Speicherplatz.

Q: Wie hängt Pascalsches Dreieck mit Binomialkoeffizienten zusammen?

Der Eintrag k der Zeile r , wobei beide ab 0 gezählt werden, ist der Binomialkoeffizient C(r, k) , also die Anzahl der Möglichkeiten, k Elemente aus r auszuwählen. Die Regel, dass jeder Eintrag die Summe der beiden Einträge darüber ist, entspricht der Identität C(r, k) = C(r-1, k-1) + C(r-1, k) . Deshalb ergibt die Zeile r auch die Summe 2^r .

Q: Kannst du eine Zeile berechnen, ohne die darüberliegenden Zeilen aufzubauen?

Ja. Beginne mit 1 und berechne jeden nächsten Eintrag aus dem vorherigen: C(r, k) = C(r, k-1) × (r-k+1) / k . Multipliziere vor dem Teilen, damit die Division aufgeht, und verwende für das Produkt eine 64-Bit-Ganzzahl. Zeile r benötigt dann O(r) Zeit und keine anderen Zeilen.

Q: Warum ist Pascalsches Dreieck ein Problem der dynamischen Programmierung?

Jeder Eintrag hängt von zwei kleineren Teilproblemen ab, den Einträgen darüber, und diese Teilprobleme überschneiden sich stark: Bei einfacher Rekursion werden sie immer wieder neu berechnet. Wenn du die Zeilen der Reihe nach aufbaust, speicherst du jedes Teilproblem einmal und verwendest es wieder, wodurch aus exponentiellem Aufwand O(n²) wird.

LeichtDynamische Programmierung

+10

Im Pascalschen Dreieck ist die erste Zeile [1]. Jede spätere Zeile hat einen Eintrag mehr, beginnt und endet mit 1, und jeder Eintrag dazwischen ist die Summe der beiden Einträge direkt darüber. Du erhältst eine ganze Zahl numRows. Gib die ersten numRows Zeilen des Dreiecks zurück, beginnend mit der obersten Zeile, wobei jede Zeile ein Array aus ganzen Zahlen ist.

Funktion

generate(numRows: integer) → integer-2d-array

numRowsinteger: wie viele Zeilen des Dreiecks aufgebaut werden sollen
Gibt zurückinteger-2d-array: die ersten numRows Zeilen, oberste Zeile zuerst

Einschränkungen

1 ≤ numRows ≤ 30
Jeder Eintrag der ersten 30 Zeilen passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl. Der größte ist 77558760 und befindet sich in der Mitte von Zeile 30.

Beispiele

Eingabe: numRows = 5
Ausgabe: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Erklärung: Jeder innere Eintrag addiert die beiden darüber. In der vierten Zeile gilt: 3 = 1 + 2 und 3 = 2 + 1. In der fünften Zeile gilt: 4 = 1 + 3, 6 = 3 + 3 und 4 = 3 + 1.

Eingabe: numRows = 1
Ausgabe: [[1]]
Erklärung: Bei einer Zeile besteht das Dreieck nur aus seiner Spitze, [1].

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du nur die letzte Zeile in einem einzelnen Array erstellen und sie Zeile für Zeile direkt aktualisieren, anstatt die darüberliegenden Zeilen beizubehalten? In welche Richtung muss die innere Schleife laufen, und warum?

Tipps

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

0 von 3 geöffnet

Lösung

Die Regel, die das Dreieck definiert, ist rekursiv: Ein Eintrag ist die Summe zweier Einträge in der Zeile darüber. Wenn du diese Regel für jeden Eintrag von Grund auf neu auswertest, berechnest du dieselben Werte immer wieder, und der Aufwand verdoppelt sich mit jeder Zeile. Die Zeilen, die du zurückgeben sollst, sind genau die gespeicherten Antworten auf diese kleineren Teilprobleme. Baue das Dreieck also von oben nach unten auf und lies jede Zeile aus der Zeile ab, die du davor erstellt hast.

Berechne jeden Eintrag rekursiv

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

Idee

Nummeriere die Zeilen und die Positionen innerhalb einer Zeile ab 0. Aus der Definition des Dreiecks wird eine Funktion: entry(row, col) ist 1, wenn col 0 oder gleich row ist, also an den beiden Rändern, und andernfalls ist es entry(row-1, col-1) + entry(row-1, col). Rufe sie für jede Position in jeder Zeile auf, und du erhältst das Dreieck. Das ist korrekt, weil es wortwörtlich die Definition ist.

Das Problem ist die Anzahl der Aufrufe. Die Rekursion endet nur an den Rändern, wo sie 1 zurückgibt. Daher erfordert die Berechnung eines Eintrags mit dem Wert v etwa 2v Aufrufe. Die Werte in Zeile r ergeben zusammen bis zu 2^r, sodass die 30 Zeilen insgesamt etwa 2^31 Aufrufe benötigen – mehr als zwei Milliarden. Dieselben kleinen Einträge werden millionenfach neu berechnet: entry(2, 1) steckt unter fast jedem darunterliegenden Wert.

Algorithmus

Schreibe entry(row, col): Gib 1 zurück, wenn col 0 ist oder col gleich row ist.
Gib andernfalls entry(row-1, col-1) + entry(row-1, col) zurück.
Sammle für jede row von 0 bis numRows-1 für jedes col von 0 bis row den Wert entry(row, col).
Gib die Liste der Zeilen zurück.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Erstelle jede Zeile aus der darüberliegenden Zeile

Idee

Die rekursive Version fragt immer wieder Einträge früherer Zeilen ab, und diese Zeilen berechnest du ohnehin. Berechne die Zeilen also der Reihe nach von oben nach unten und lies beim Füllen der Zeile r die benötigten Werte direkt aus der bereits berechneten Zeile r-1. Jeder Eintrag erfordert dann eine Addition. Das ist dynamische Programmierung in ihrer einfachsten Form: Die Tabelle der kleineren Ergebnisse ist selbst die Ausgabe.

Beginne die Zeile r mit r + 1 Einsen, wodurch beide Ränder festgelegt werden. Setze dann für jede innere Position c von 1 bis r-1 ihren Wert auf above[c-1] + above[c]. Die Zeilen 0 und 1 haben keine inneren Positionen, daher bleiben sie ohne Sonderfall [1] und [1, 1].

Das Dreieck hat 1 + 2 + ... + n, also etwa n²/2 Einträge, und jeder benötigt konstante Zeit. Daher beträgt der Aufwand O(n²). Abgesehen von der Ausgabe, die du ohnehin zurückgeben musst, benötigt die Methode keinen zusätzlichen Speicher. Für numRows = 30 sind das 465 Einträge statt zwei Milliarden Aufrufen.

Algorithmus

Beginne mit einer leeren Liste von Zeilen.
Erstelle für jede row von 0 bis numRows-1 row + 1 Einsen.
Setze für jede col von 1 bis row-1 den Wert auf die Summe der Positionen col-1 und col der vorherigen Zeile.
Füge die Zeile hinzu und fahre fort. Gib die Liste zurück.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Stolperfallen und Grenzfälle

Die Schleifen sind kurz, daher betreffen die Fehler die Grenzen und die ersten Zeilen.

numRows + 1 Zeilen zurückgeben. Wenn du die Zeilen ab 0 nummerierst, ist die letzte benötigte Zeile die Zeile numRows-1.
Die innere Schleife über die Ränder laufen lassen. Position 0 hat keinen linken Elternknoten und Position row keinen rechten Elternknoten. Daher führt das Auslesen von above[col-1] oder above[col] dort zu einem Zugriff außerhalb des gültigen Bereichs. Fülle nur die Positionen 1 bis row-1.
Einen Bereich schreiben, der bei kleinen Zeilen fehlschlägt. Swifts 1..<row stürzt ab, wenn row 0 ist, und Rs 2:(row-1) zählt bis 1 herunter, wenn row 2 ist. Füge eine Prüfung hinzu oder beginne die inneren Positionen mit Einsen, sodass die Zeilen 0 und 1 keine Schleife benötigen.
Einträge mithilfe von Fakultäten berechnen. C(29, 14) passt in einen int, aber 29! läuft selbst bei einer 64-Bit-Ganzzahl über. Daher gibt eine auf Fakultäten basierende Formel in den unteren Zeilen falsche Zahlen aus.
Für jede Zeile dasselbe Array wiederverwenden. Wenn du jedes Mal dasselbe Array hinzufügst und es anschließend änderst, wird jede Zeile in der Antwort zur letzten.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Erzeugen des Pascalschen Dreiecks?

Das Erstellen jeder Zeile aus der darüberliegenden benötigt für n Zeilen O(n²) Zeit, weil das Dreieck etwa n²/2 Einträge hat und jeder davon durch eine einzelne Addition berechnet wird. Das ist optimal, da du jeden Eintrag der Ausgabe schreiben musst. Abgesehen von der Ausgabe benötigt es O(1) zusätzlichen Speicherplatz.

Wie hängt Pascalsches Dreieck mit Binomialkoeffizienten zusammen?

Der Eintrag k der Zeile r, wobei beide ab 0 gezählt werden, ist der Binomialkoeffizient C(r, k), also die Anzahl der Möglichkeiten, k Elemente aus r auszuwählen. Die Regel, dass jeder Eintrag die Summe der beiden Einträge darüber ist, entspricht der Identität C(r, k) = C(r-1, k-1) + C(r-1, k). Deshalb ergibt die Zeile r auch die Summe 2^r.

Kannst du eine Zeile berechnen, ohne die darüberliegenden Zeilen aufzubauen?

Ja. Beginne mit 1 und berechne jeden nächsten Eintrag aus dem vorherigen: C(r, k) = C(r, k-1) × (r-k+1) / k. Multipliziere vor dem Teilen, damit die Division aufgeht, und verwende für das Produkt eine 64-Bit-Ganzzahl. Zeile r benötigt dann O(r) Zeit und keine anderen Zeilen.

Warum ist Pascalsches Dreieck ein Problem der dynamischen Programmierung?

Jeder Eintrag hängt von zwei kleineren Teilproblemen ab, den Einträgen darüber, und diese Teilprobleme überschneiden sich stark: Bei einfacher Rekursion werden sie immer wieder neu berechnet. Wenn du die Zeilen der Reihe nach aufbaust, speicherst du jedes Teilproblem einmal und verwendest es wieder, wodurch aus exponentiellem Aufwand O(n²) wird.

Python

def generate(numRows):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

numRows = 5

Erwartet

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]