Climbing Stairs

Count distinct ways to climb a staircase with 1 or 2 steps.

fibonacci dp counting

You are climbing a staircase. It takes n steps to reach the top, where n is a non-negative integer. Each time you can either climb 1 step or 2 steps. Write a function `climb_stairs(n: int) -> int` that returns the number of distinct ways you can climb to the top.

Define `ways(0) = 1` (an empty way) and `ways(1) = 1`. The answer should be computed efficiently enough for n up to 90 without recursion depth issues.

Constraints

- 0 <= n <= 90
- The answer fits within a signed 64-bit integer.
- Time complexity: O(n) is acceptable, but you must avoid exponential recursion.

Example

>>> climb_stairs(2)
2
>>> climb_stairs(3)
3
>>> climb_stairs(4)
5
>>> climb_stairs(0)
1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try base cases: climb_stairs(0) and climb_stairs(1) are both 1.

For n >= 2, the answer is the sum of the answers for n-1 and n-2.

Use a loop with two variables instead of recursion to avoid redundant computation.

This is the Fibonacci sequence shifted by one.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.