Climbing Stairs

Difficulty: Easy · Topic: Dynamic programming

You climb a staircase of n steps, taking 1 or 2 steps at a time. Return the number of distinct ways to reach the top. The ways to reach step i equal the ways to reach i-1 plus i-2 — it's the Fibonacci recurrence.

Examples

climbing_stairs(2)
→ 2

1+1 or 2.

climbing_stairs(3)
→ 3

1+1+1, 1+2, 2+1.

climbing_stairs(5)
→ 8

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.