Med.dynamic programmingrecursion

Climbing Stairs

Count the distinct ways to climb n steps taking one or two at a time.

You are climbing a staircase with n steps. Each move takes you up either one step or two. Return how many distinct sequences of moves reach the top.

Constraints

  • 1 ≤ n ≤ 45

Stuck?

Read the Dynamic Programming tutorial, it covers what you need to know.

Examples

Input
n = 2
Output
2
Why
Either 1 + 1 or a single 2.
Input
n = 3
Output
3
Why
1+1+1, 1+2, or 2+1. Order matters, so 1+2 and 2+1 are different.
Input
n = 5
Output
8
Why
The counts follow the Fibonacci numbers.

Submitting also runs 6 hidden tests.

Limits

2000 ms and 256 MB per test case.

You can run the examples without an account. Sign in to submit against the hidden cases and keep your progress.

Run checks the examples above. Submit checks those plus the hidden cases.