Pytanie: Wchodzisz po schodach. Aby dostać się na szczyt, potrzeba n kroków. Za każdym razem możesz zrobić 1 krok lub 2 kroki. Na ile różnych sposobów można dostać się na szczyt?
Opis problemu: http://oj.leetcode.com/problems/climbing-stairs/
Ten problem może początkowo wydawać się trudny, ale kiedy pomyślisz przez chwilę, może się okazać, że jest to takie proste. Odpowiedzią są liczby Fibonacciego (patrz tutaj, tutaj )
Cóż, oryginalne liczby Fibonacciego są zdefiniowane jako sekwencje:
W przypadku tego problemu musimy tylko trochę zmodyfikować:
a 
ponieważ tylko dla 1 kroku istnieje tylko 1 odrębna droga, a dla 2 kroków mamy dwa rozwiązania: 1 + 1 lub 2.
Reszta to seria Fibonacciego. Ponieważ 
z obecnej pozycji jesteśmy prawdopodobnie z dwóch poprzednich pozycji, F(n-1) i F(n-2).
Możesz użyć rekurencji, ale można to rozwiązać za pomocą bardziej efektywnego rozwiązania iteracyjnego.
Lub wolisz prostszą funkcję rekurencyjną:
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};Uwaga: Funkcja rekurencyjna zwróci LIMIT CZASU PRZEKROCZONY w teście 44. Dzieje się tak dlatego, że funkcja rekurencyjna zwykle oblicza wartości pośrednie wiele razy. Na przykład 
, 
. 
jest obliczana dwukrotnie.