#70 Climbing Stairs
You're at the bottom of a staircase with n steps. Each move, you may climb
either 1 step or 2 steps. Count how many distinct sequences of moves get you
to the top.
Order matters: taking 1-then-2 is a different way than 2-then-1.
Examples
Input
n = 2Output
2Two ways: (1, 1) or (2).
Input
n = 3Output
3Three ways: (1, 1, 1), (1, 2), (2, 1).
Constraints
1 ≤ n ≤ 45The answer fits in a 32-bit signed integer for this range
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.