We need to count the total number of distinct ways to reach step n, starting from step 0. At each position, we have two choices: take one step or take two steps. The order matters, so "1 step then 2 steps" is different from "2 steps then 1 step."

To arrive at step n, the last move was either a single step from step n-1 or a double step from step n-2. Every path ends in one of these two moves and no path ends in both, so the two groups are disjoint and together cover all paths. The number of ways to reach step n is therefore the sum of the ways to reach step n-1 and the ways to reach step n-2.

In recurrence form: ways(n) = ways(n-1) + ways(n-2), with base cases ways(1) = 1 and ways(2) = 2. The answers 1, 2, 3, 5, 8, ... are the Fibonacci numbers shifted by one position.

Key Constraints:

Intuition

The recurrence translates directly into a recursive function: the ways to reach step n equal the ways to reach step n-1 plus the ways to reach step n-2. The recursion stops at the base cases: 1 way to reach step 1 (one single step) and 2 ways to reach step 2 (two singles, or one double).

This computes the correct answer but recalculates the same subproblems many times. Computing climbStairs(5) requires climbStairs(4) and climbStairs(3), and climbStairs(4) itself calls climbStairs(3) again. As n grows, the tree of recursive calls expands exponentially.

Algorithm

Example Walkthrough

Input: n = 5

The recursion unfolds as a tree, branching until it hits the base cases:

climbStairs(5) returns 8. Even at n = 5, climbStairs(3) is computed twice and climbStairs(2) three times. The duplication compounds at every level of the tree, which is what makes the running time exponential.

Code

All of that repeated work recomputes values the program already produced earlier. The next approach stores each result the first time it is computed.

Intuition

The fix for the brute force recursion is to cache the result of every subproblem. Before computing climbStairs(k), check whether the answer is already stored. If it is, return it immediately. If not, compute it, store it, and return it.

This technique is called memoization. There are only n distinct subproblems (steps 1 through n), each is computed once, and every later request for the same subproblem is answered from the cache in O(1). The exponential call tree collapses into a linear chain of first-time computations.

Algorithm

Example Walkthrough

Input: n = 5

The animation tracks the memo array. The base cases (steps 1 and 2) return their values directly and are never written to the array; only steps 3 through 5 get cached.

Code

Memoization still costs O(n) space for the memo array and the recursion stack. The recurrence only ever reads the two values before it, so the final approach computes the answer iteratively with two variables.

Intuition

Since ways(n) = ways(n-1) + ways(n-2), we can compute the answer iteratively, starting from the base cases and working up to n. The recursion in Approach 2 already filled the memo in this order (1, 2, 3, ..., n); a loop produces the same sequence without any call stack.

Each new value depends only on the two values before it, so instead of maintaining an array of size n, we keep two variables and shift them forward after every iteration. This space optimization applies to any 1D recurrence with a fixed lookback: when a state depends only on the previous k states, k variables replace the whole array. Here k = 2, so O(n) storage drops to O(1).

Algorithm

Example Walkthrough

Input: n = 5

The animation shows the values as they would fill a dp array. The algorithm itself stores only the two highlighted positions, prev2 and prev1, which slide right by one each iteration.

Code