Climbing Stairs

The key idea

To reach step n you either take one step from n-1 or a double step from n-2, and those two groups of paths never overlap. So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence. Only the last two results matter, so two rolling variables give O(1) space.

Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints

1 <= n <= 45

Examples

Input: n = 2 Output: 2

Input: n = 3 Output: 3

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →