Climbing Stairs
Du stehst am Fuß einer Treppe mit n Stufen. Bei jedem Schritt gehst du entweder 1 oder 2 Stufen hinauf. Zwei Aufstiege zählen als unterschiedlich, wenn sich ihre Schrittfolgen unterscheiden, also sind 1, 2 und 2, 1 zwei Möglichkeiten. Deine Funktion erhält n und gibt die Anzahl der verschiedenen Möglichkeiten zurück, die oberste Stufe zu erreichen.
Funktion
- ninteger
- die Anzahl der Stufen in der Treppe
- Gibt zurückinteger
- die Anzahl der verschiedenen Folgen aus 1er- und 2er-Schritten, die Stufe n erreichen
Einschränkungen
1 ≤ n ≤ 45- Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl:
n = 45ergibt1836311903.
Beispiele
- Eingabe
- n = 3
- Ausgabe
- 3
- Erklärung
- Drei Stufen kann man als
1, 1, 1, als1, 2oder als2, 1erklimmen, also gibt es 3 Möglichkeiten.
- Eingabe
- n = 5
- Ausgabe
- 8
- Erklärung
- Jeder Aufstieg zu Schritt 5 endet mit einem 1-Schritt von Schritt 4 (5 Möglichkeiten, dorthin zu gelangen) oder einem 2-Schritt von Schritt 3 (3 Möglichkeiten), also lautet die Antwort
5 + 3 = 8.
+13 versteckte Tests beim Einreichen
Weiterführende Frage
Was ist, wenn einige Stufen beschädigt sind und du sie möglicherweise nie betreten kannst? Wie ändert sich die Rekursion, und wie lautet die Anzahl für eine beschädigte Stufe?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Betrachte den letzten Schritt eines beliebigen Aufstiegs zur Stufe
n. Wo hättest du unmittelbar davor stehen können?Jeder Aufstieg zu Stufe
nendet mit einem Schritt von Stufen-1oder mit zwei Schritten von Stufen-2, niemals mit beidem. Die Anzahl fürnist also die Anzahl fürn-1plus die Anzahl fürn-2.Beginne mit den Anzahlen für 1 Schritt (1 Möglichkeit) und 2 Schritte (2 Möglichkeiten) und arbeite dich nach oben. Du brauchst immer nur die letzten beiden Anzahlen, und jede neue Anzahl ist ihre Summe.
Lösung
Jeden einzelnen Weg aufzulisten, funktioniert nicht: Eine Treppe mit 45 Stufen hat 1836311903 davon. Der Schlüssel liegt im letzten Schritt. Jeder Weg zu Stufe n führt direkt vor dem Ende über Stufe n-1 oder Stufe n-2. Daraus ergibt sich ways(n) = ways(n-1) + ways(n-2), die Fibonacci-Rekursion. Berechne sie von unten nach oben, und zwei Variablen reichen aus.
Einfache Rekursion beim letzten Zug
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Teile die Aufstiege zu Stufe n nach ihrem letzten Schritt auf. Bei einem Aufstieg, der mit einem Schritt endet, stand man davor auf Stufe n-1, und es gibt ways(n-1) solche Aufstiege. Bei einem Aufstieg, der mit zwei Schritten endet, stand man auf Stufe n-2, und davon gibt es ways(n-2). Jeder Aufstieg endet auf die eine oder andere Weise, und keiner endet auf beide Arten, also gilt ways(n) = ways(n-1) + ways(n-2).
Die Rekursion benötigt zwei Basisfälle. Für eine Stufe gibt es einen Aufstieg, und für zwei Stufen gibt es zwei Aufstiege (1, 1 und 2). In beiden Fällen entspricht die Antwort n, daher gibt die Funktion n zurück, wenn n ≤ 2, andernfalls die Summe.
Die Antwort ist richtig, aber der Aufwand explodiert. climbStairs(5) fragt zweimal nach Stufe 3 und dreimal nach Stufe 2, insgesamt also 9 Aufrufe, und die Anzahl der Aufrufe wächst ähnlich wie die Antworten selbst. Für n = 45 führt die Funktion 2269806339 Aufrufe aus, etwa 2.3 × 10^9 – viel zu viele für ein Zeitlimit. Die Rekursion ist nur n Ebenen tief, daher benötigt der Aufrufstapel O(n) Speicherplatz.
Algorithmus
- Wenn
n ≤ 2, gibnzurück. - Zähle die Aufstiege, die mit einem rekursiven Aufruf die Stufe
n-1erreichen. - Zähle die Aufstiege, die mit einem zweiten rekursiven Aufruf die Stufe
n-2erreichen. - Gib die Summe der beiden Anzahlen zurück.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)Rekursion mit einem Memo
Idee
Die Rekursion ist nur deshalb langsam, weil sie vergisst. Jede Anzahl hängt allein von k ab, also ändert sie sich nicht mehr, sobald du die Anzahl für Schritt k kennst. Lege ein Memo an, ein Array mit einem Platz pro Schritt, und speichere dort jede Anzahl, wenn du sie zum ersten Mal berechnest. Jede spätere Anfrage für denselben Schritt liest den Platz aus, statt erneut zu rekursieren.
Nun wird jede der Anzahlen von Schritt 3 bis Schritt n genau einmal berechnet, mit einer Addition. Für n = 5 gehen die Aufrufe einmal bis zu Schritt 2 hinunter, dann kommen die Antworten als 3, 5 und 8 zurück, und die zweite Anfrage für Schritt 3 ist ein Nachschlagen. Das ist eine Laufzeit von O(n) statt Milliarden von Aufrufen.
Das Memo enthält n + 1 Zahlen und die Rekursion ist weiterhin n Ebenen tief, daher beträgt der Speicherbedarf O(n). Eine 0 in einem Platz bedeutet, dass der Wert noch nicht bekannt ist. Das ist unbedenklich, weil jede tatsächliche Anzahl mindestens 1 beträgt.
Algorithmus
- Erstelle ein Memo mit
n + 1Plätzen, alle mit 0. - Gib im rekursiven Hilfsverfahren
kzurück, wennk ≤ 2. - Wenn der Memo-Platz für
k0 ist, fülle ihn mit der Summe der Ergebnisse des Hilfsverfahrens fürk-1undk-2. - Gib den Memo-Platz zurück.
- Rufe das Hilfsverfahren mit
nauf.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)Von unten nach oben mit zwei Variablen
Idee
Dreh die Rekursion um. Statt oben anzufangen und nach unten zu fragen, beginnst du unten und arbeitest dich nach oben. Wenn du die Anzahl für Schritt k berechnest, sind die Anzahlen für k-1 und k-2 bereits bekannt, und ältere Werte werden nie wieder gelesen. Daher ersetzen zwei Variablen das gesamte Memo.
Lass prev die Anzahl für Schritt k-2 und curr die Anzahl für Schritt k-1 enthalten. Beginne mit prev = 1 und curr = 2, den Anzahlen für Schritt 1 und 2. Addiere sie bei jedem Schritt zu next und verschiebe dann das Paar nach vorne. Für n = 5 bewegt sich das Paar von (1, 2) zu (2, 3), (3, 5) und (5, 8), und curr = 8 ist die Antwort.
Die Schleife läuft n-2 Mal und führt jeweils eine Addition aus, benötigt also O(n) Zeit und hält drei Ganzzahlen, also O(1) Speicherplatz. Berechne next, bevor du prev überschreibst, sonst verwendet die Summe den falschen Wert.
Algorithmus
- Wenn
n ≤ 2ist, gibnzurück. - Setze
prev = 1undcurr = 2. - Berechne für
kvon 3 bisnnext = prev + curr, setze dannprev = currundcurr = next. - Gib
currzurück.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
Stolperfallen und Grenzfälle
Die Rekursion ist kurz, daher liegen die meisten Fehler in den Basisfällen, der Laufzeit und der 32-Bit-Grenze.
- Die einfache Rekursion abgeben. Sie besteht die kleinen Tests und benötigt dann für
n = 45etwa2.3 × 10^9Aufrufe. Speichere jeden Zählwert nur einmal. - Falsche Basisfälle. Bei zwei Stufen gibt es zwei Aufstiege:
1, 1und2. Wenn du fürn = 21 zurückgibst, verschiebt sich jede spätere Antwort: Fürn = 3erhieltest du dann 2 statt 3. - Auswahlmöglichkeiten statt Folgen zählen.
1, 2und2, 1sind zwei Aufstiege. Wenn du nur zählst, wie viele 2er-Schritte du machst, ergibt dasn/2 + 1— bein = 5also 3 statt 8. - Eine Tabelle ohne Schutzbedingung füllen. Bei
n = 1bietet eine Tabelle mitn + 1 = 2Plätzen keinen Platz für die Anzahl der Möglichkeiten für Schritt 2. Gibnsofort zurück, wennn ≤ 2gilt. - Einen Schritt zu weit gehen. Die Anzahl für 45 Stufen, 1836311903, passt in 32 Bit, aber die Anzahl für 46 Stufen beträgt 2971215073 und passt nicht. Eine Schleife, die einen zusätzlichen Wert berechnet, läuft in Java, C oder C# über und ergibt eine negative Zahl.
Häufige Fragen4
Warum ist Treppensteigen ein Fibonacci-Problem?
Jeder Aufstieg zu Stufe n endet mit einem Schritt von n-1 oder zwei Schritten von n-2 aus, also ways(n) = ways(n-1) + ways(n-2). Das ist die Fibonacci-Regel. Mit ways(1) = 1 und ways(2) = 2 lauten die Anzahlen 1, 2, 3, 5, 8, 13, also die um eine Stelle verschobene Fibonacci-Folge: ways(n) = F(n+1).
Wie hoch ist die Zeitkomplexität des Treppensteigens?
Die Schleife von unten nach oben führt n-2 Additionen aus und benötigt daher O(n) Zeit und O(1) zusätzlichen Speicherplatz. Die einfache Rekursion ist exponentiell: Die Anzahl der Aufrufe wächst pro Schritt um etwa den Faktor 1.618 und erreicht bei n = 45 den Wert 2269806339, also ungefähr 2.3 × 10^9. Durch Memoisierung benötigt die Rekursion nur noch O(n) Zeit und O(n) Speicherplatz.
Was ist der Unterschied zwischen Memoisierung und der Bottom-up-Lösung?
Memoisierung behält die rekursive Funktion bei und speichert jedes Ergebnis zwischen, wenn es zum ersten Mal berechnet wird. Sie arbeitet also von oben nach unten und benötigt den Aufrufstapel sowie eine Tabelle. Die Bottom-up-Schleife berechnet die Anzahl in aufsteigender Reihenfolge, sodass jeder benötigte Wert bereits bekannt ist und keine Rekursion erforderlich ist. Beide benötigen O(n) Aufwand. Bei der Schleife kannst du außerdem die Tabelle weglassen und zwei Zahlen behalten.
Wie löst man „Treppensteigen“ mit Schritten von 1, 2 oder 3?
Teile die Aufstiege wieder nach ihrem letzten Schritt auf: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Beginne mit ways(0) = 1 (dem leeren Aufstieg), ways(1) = 1 und ways(2) = 2 und behalte die letzten drei Anzahlen statt zwei im Blick. Die Laufzeit bleibt O(n) und der Speicherbedarf O(1).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def climbStairs(n):
# Schreibe hier deinen CodeFall 1
Fall 2
Eingabe
n = 3
Erwartet
3