Dynamic Programming · 033Easy
Climbing Stairs
You are climbing a staircase of n steps. Each move you may climb 1 or 2 steps. Return how many distinct ways you can reach the top.
Constraints
- 1 <= n <= 45
Examples
climbStairs(2) -> 2 // 1+1, 2 climbStairs(3) -> 3 // 1+1+1, 1+2, 2+1 climbStairs(1) -> 1 climbStairs(4) -> 5 climbStairs(5) -> 8 climbStairs(10) -> 89
Edge cases
- n = 1 and n = 2 are the base cases.
- Order matters: 1+2 and 2+1 are different ways.
Show the target complexity (spoiler)
- Naive
- O(2^n) time — recurse over every possible move sequence.
- Target
- O(n) time, O(1) space — ways(n) = ways(n-1) + ways(n-2), carried in two rolling variables.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/033-climbing-stairs.js ./practice c 033