Description
Count ways to reach stair n, taking either one or two steps at a time; 1 <= n <= 45.
Solution
def climb_stairs(n):
previous, current = 1, 1
for _ in range(n):
previous, current = current, previous+current
return previousExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[1]- Output
1
Only one single step is possible.
Example 2
- Input
[3]- Output
3
The sequences are 111, 12, and 21.
Example 3
- Input
[5]- Output
8
The recurrence adds the counts for stairs four and three.
Approach
The number of ways is the sum for the preceding two stairs. Roll two states forward.
Time & space
O(n) time; O(1) auxiliary space, where n is the stair count.