mafeshsho8lmafeshsho8l
Get Started
All coding questions

Climbing Stairs

easy
Blind 75NeetCode 150dynamic-programmingmath

Problem

You are climbing a staircase that takes n steps to reach the top. Each move you may climb one or two steps. Count the number of distinct ways to reach the top.

Examples

Input: n = 2
Output: 2
Either two single steps or one double step.
Input: n = 3
Output: 3
1+1+1, 1+2, or 2+1.

Constraints

  • • 1 <= n <= 45
Hints(tap to reveal)
  • 1. Ways to reach step n come from step n-1 and step n-2.
  • 2. This is the Fibonacci recurrence.
Optimal approach(spoiler)
  1. Let ways(i) be the number of ways to reach step i.
  2. Observe ways(i) equals ways(i-1) plus ways(i-2).
  3. Iterate upward keeping only the last two values.
  4. Return the value at step n.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor