Algorithms and Data Structures · Middle · Question 42 of 75
Climbing stairs: you can step 1 or 2 stairs at a time. How many ways are there to climb n stairs?
- 1
ways(n) = 2 ** n, because each step has two choices - 2
ways(n) = n * 2, one or two steps for each stair - ✓Correct answer:
ways(n) = ways(n - 1) + ways(n - 2), the Fibonacci recurrence
Explanation
The last move is either a single step from stair n - 1 or a double step from n - 2, so the counts add up. With two variables it's O(n) time and O(1) memory.