Climbing Stairs
Easy · Dynamic Programming · Math · Dynamic Programming · Memoization
Problem
You are climbing a staircase of n steps. Each move takes you up 1 or 2 steps. How many distinct ways can you reach the top?
Examples
Input: n = 2 Output: 2
1+1, or 2.
Input: n = 3 Output: 3
1+1+1, 1+2, 2+1.
Constraints
- 1 <= n <= 45
Approaches
- Naive recursion (exponential — do not submit) — time O(2ⁿ), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
