Programmierübung – Treppensteigen – Fibonacci-Zahlen – C++ – Online Judge
Frage: Sie steigen Treppen. Es dauert n Schritte, um an die Spitze zu gelangen. Sie können jedes Mal 1 Schritt oder 2 Schritte machen. Wie viele verschiedene Wege, um an die Spitze zu gelangen?
Problembeschreibung: http://oj.leetcode.com/problems/climbing-stairs/
Dieses Problem mag auf den ersten Blick schwierig erscheinen, aber wenn Sie eine Sekunde nachdenken, finden Sie es vielleicht so einfach. Die Antwort lautet Fibonacci-Zahlen (siehe hier, hier )
Nun, die ursprünglichen Fibonacci-Zahlen sind als Folgen definiert:
Für dieses Problem müssen wir nur ein wenig modifizieren:
und weil es für nur 1 Schritt nur 1 eindeutigen Weg gibt und wir für 2 Schritte zwei Lösungen haben: 1 + 1 oder 2.
Der Rest ist als Fibonacci-Reihe. Denn von der aktuellen Position aus sind wir möglicherweise von den beiden vorherigen Positionen F(n-1) und F(n-2).
Sie können Rekursion verwenden, aber dies kann durch eine effektivere iterative Lösung gelöst werden.
Oder Sie bevorzugen eine einfachere rekursive Funktion:
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
Hinweis: Die rekursive Funktion ergibt ZEITLIMIT ÜBERSCHRITTEN bei Test 44. Das liegt daran, dass die rekursive Funktion normalerweise viele Male Zwischenwerte berechnet. Zum Beispiel , . wird zweimal berechnet.