You are climbing a staircase that has n steps. Each time you may climb either 1 step or 2 steps. In how many distinct ways can you reach the top (step n)?
Two ways are different if, at some point in the climb, the size of the step taken differs. Return the total count.
A single line containing one integer n.
A single line containing one integer: the number of distinct ways to climb to the top.
For n = 3 the ways are 1+1+1, 1+2, and 2+1, so the answer is 3.
Example 1
Input
3
Expected
3
Explanation
From the bottom the distinct step sequences are 1+1+1, 1+2, and 2+1, giving 3 distinct ways.
Example 2
Input
5
Expected
8
Explanation
There are 8 distinct ways to climb 5 steps; this equals the 6th Fibonacci number, matching the recurrence ways(n) = ways(n-1) + ways(n-2).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →