Ways to Climb Stairs
A staircase has n steps. You start at the bottom and want to reach the top.
In one move you climb either 1 step or 2 steps.
Return the number of different ways to reach the top. Two ways are different if their lists of moves are different. For example, 1 then 2 and 2 then 1 are two different ways.
Hint
Your last move to step n came from step n - 1 (a 1-step move) or from step n - 2 (a 2-step move). So ways(n) = ways(n - 1) + ways(n - 2). Plain recursion repeats the same work many times and is too slow for n = 45. Keep the last two answers in a loop instead.
Examples
Example 1
- Input:
- 1
- Output:
- 1
There is only one way: one 1-step move.
Example 2
- Input:
- 4
- Output:
- 5
The five ways are 1+1+1+1, 2+1+1, 1+2+1, 1+1+2 and 2+2.
Example 3
- Input:
- 6
- Output:
- 13
ways(5) = 8 ways end with a 1-step move, and ways(4) = 5 ways end with a 2-step move. 8 + 5 = 13.
Constraints
1 <= n <= 45- The answer fits in a 32-bit signed integer.
Run checks your code against the 3 examples. Submit checks it against all 48 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.