Climbing Stairs

Podziel wspinaczki na stopień n ze względu na ich ostatni ruch. Wspinaczka kończąca się krokiem o 1 stopień wcześniej znajdowała się na stopniu n-1, a takich wspinaczek jest ways(n-1). Wspinaczka kończąca się krokiem o 2 stopnie wcześniej znajdowała się na stopniu n-2, a takich wspinaczek jest ways(n-2). Każda wspinaczka kończy się na jeden albo drugi sposób, a żadna nie kończy się na oba sposoby, więc ways(n) = ways(n-1) + ways(n-2).

Rekurencja wymaga dwóch przypadków bazowych. Na jeden stopień prowadzi jedna wspinaczka, a na dwa stopnie — dwie wspinaczki (1, 1 i 2). W obu przypadkach odpowiedź jest równa n, więc funkcja zwraca n, gdy n ≤ 2, a w przeciwnym razie sumę.

Odpowiedź jest poprawna, ale liczba obliczeń gwałtownie rośnie. climbStairs(5) dwukrotnie wywołuje obliczenie dla stopnia 3 i trzykrotnie dla stopnia 2 — łącznie 9 wywołań — a ich liczba rośnie podobnie jak same odpowiedzi. Dla n = 45 funkcja wykonuje 2269806339 wywołań, czyli około 2.3 × 10^9, zdecydowanie za dużo, by zmieścić się w limicie czasu. Rekurencja ma głębokość zaledwie n, więc stos zajmuje O(n) miejsca.

Rekurencja jest powolna tylko dlatego, że zapomina. Każda liczba zależy wyłącznie od k, więc gdy znasz już liczbę dla kroku k, nigdy się ona nie zmienia. Zachowaj pamięć podręczną — tablicę z jednym miejscem na każdy krok — i zapisz w niej każdą liczbę przy pierwszym obliczeniu. Każde kolejne żądanie dotyczące tego samego kroku odczytuje wartość z tego miejsca, zamiast ponownie wywoływać rekurencję.

Teraz każda z liczb od kroku 3 do kroku n jest obliczana raz, przy użyciu jednego dodawania. Dla n = 5 wywołania schodzą do kroku 2 tylko raz, a następnie wyniki wracają jako 3, 5 i 8; drugie żądanie dotyczące kroku 3 korzysta już z odczytu. Złożoność czasowa wynosi O(n) zamiast miliardów wywołań.

Pamięć podręczna przechowuje n + 1 liczb, a rekurencja nadal sięga n poziomów w głąb, więc złożoność pamięciowa wynosi O(n). 0 w danym miejscu oznacza, że wartość nie jest jeszcze znana, co jest bezpieczne, ponieważ każda rzeczywista liczba wynosi co najmniej 1.

Odwróć rekurencję. Zamiast zaczynać od góry i pytać o kolejne wartości w dół, zacznij od dołu i buduj w górę. Gdy obliczasz liczbę sposobów dla kroku k, liczby dla kroków k-1 i k-2 są już znane, a do żadnych wcześniejszych już się nie odwołujesz. Całe memo można więc zastąpić dwiema zmiennymi.

Niech prev przechowuje liczbę sposobów dla kroku k-2, a curr — liczbę sposobów dla kroku k-1. Zacznij od prev = 1 i curr = 2 — to liczby sposobów dla kroków 1 i 2. W każdym kroku dodaj je i zapisz wynik w next, a następnie przesuń parę. Dla n = 5 para zmienia się z (1, 2) na (2, 3), (3, 5) i (5, 8), a curr = 8 jest odpowiedzią.

Pętla wykonuje się n-2 razy, za każdym razem wykonując jedno dodawanie. Złożoność czasowa wynosi O(n), a algorytm przechowuje trzy liczby całkowite, więc złożoność pamięciowa wynosi O(1). Oblicz next przed nadpisaniem prev, w przeciwnym razie suma będzie korzystać z niewłaściwej wartości.