Climbing Stairs
Ways to reach step n = ways to reach n−1 plus n−2.
Approach
Each step is reached from one or two below it, so the count is the Fibonacci recurrence f(n) = f(n−1) + f(n−2). Compute bottom-up with two rolling variables instead of a full array for O(1) space.
Time complexity
O(n)
Space complexity
O(1)
Common mistake
Plain recursion without memoization, which recomputes the same subproblems exponentially.
See it run, step by step
Generate an interactive lesson for Climbing Stairs — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Climbing Stairs