Climbing Stairs

You’re climbing a staircase with n steps and can climb 1 or 2 steps at a time. In how many distinct ways can you reach the top?

Examples

Input:  n = 2
Output: 2      (1+1, 2)

Input:  n = 3
Output: 3      (1+1+1, 1+2, 2+1)

Constraints

• 1 ≤ n ≤ 45

Explanation

Recursion

The last move onto step n came either from step n − 1 (a 1-step) or from step n − 2 (a 2-step). So

$\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2), \quad \text{ways}(1) = 1,\ \text{ways}(2) = 2$

Computing this recursively recomputes the same values exponentially many times: O(2ⁿ).

Bottom-up with two variables

Each value only needs the previous two, so walk up from the bottom keeping just those: it’s the Fibonacci sequence.

This is the template for most 1-D DP: define the state, find the recurrence, fix the base cases, choose an order that computes dependencies first.

Complexity

• Time: O(n). Space: O(1).