701. Stair Climber
A lighthouse keeper climbs a spiral staircase with n stairs. On every move the keeper can either lift one foot to the next stair or stretch over one stair and land on the one after it, never going down and never skipping more than one stair.
Return the number of different sequences of moves that take the keeper from the ground to the top stair, landing exactly on it. Two sequences are different when at some move one of them takes a short step and the other a long one. Standing at the top without climbing counts as one way when n is 0.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- n = 6
- Output:
- 13
- Explanation:
Six stairs can be climbed in 13 different orders of short and long steps; for instance 2+2+2 and 1+2+1+2 are two of them.
Example 2
- Input:
- n = 9
- Output:
- 55
- Explanation:
Each new total is the sum of the previous two totals, so the counts run 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and nine stairs give 55 ways.
Constraints
0 ≤ n ≤ 45
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)