Algorytmy i struktury danych · Middle · Pytanie 42 z 75
Schody: można wejść o 1 lub 2 stopnie naraz. Na ile sposobów można wejść na n stopni?
- 1
ways(n) = 2 ** n, bo każdy krok ma dwie opcje - 2
ways(n) = n * 2, jeden lub dwa stopnie na każdy - ✓Poprawna odpowiedź:
ways(n) = ways(n - 1) + ways(n - 2), rekurencja Fibonacciego
Wyjaśnienie
Ostatni ruch to albo pojedynczy krok ze stopnia n - 1, albo podwójny z n - 2, więc liczby się sumują. Z dwiema zmiennymi to O(n) czasu i O(1) pamięci.