v9.1.1
Menu

Climbing Stairs

easyPRODynamic ProgrammingNetflix DSA

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

Example

Input
3
Output
3
Reasoning
  • Input: n is the number of steps in the staircase, here n=3n = 3. Each move climbs either 11 or 22 steps, and you must land exactly on step 33 (no overshooting).
  • What counts as a way: an ordered sequence of moves whose sizes add up to nn. Order matters, so 1+21 + 2 and 2+12 + 1 are two different ways even though they use the same moves.
  • Working the sample: the sequences summing to 33 are 1+1+11 + 1 + 1 (three moves), 1+21 + 2 and 2+12 + 1 (two moves each). Two moves of size 22 would already reach 44 and overshoot, so there are no others.
  • Output: the count of those sequences, 3, a single integer.
  • Notice that the answer grows quickly with nn: for n=1n = 1 there is 11 way, for n=2n = 2 there are 22 (1+11 + 1 and 22), and for n=4n = 4 there are already 55. Listing every sequence by hand stops being practical long before n=45n = 45.

Constraints

  • 1 <= n <= 45

Learn this in

More from Netflix DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.