Skip to main content

70. Climbing Stairs

easy

Count distinct ways to climb n stairs taking 1 or 2 steps at a time. The Fibonacci-shaped sequence — the bedrock DP introduction problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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

Example 1

Input
n = 2
Output
2

Explanation: There are two ways to climb to the top. 1. 1 step + 1 step. 2. 2 steps.

Example 2

Input
n = 3
Output
3

Explanation: 1+1+1, 1+2, 2+1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive recursion: ways(n) = ways(n-1) + ways(n-2). Exponential without memo.

Hint 2

Memoize to get O(n) time, O(n) space.

Hint 3

Notice you only need the previous two values — drop the array, use two variables.

Solution approach

Reveal approach

Bottom-up iteration with two variables. The recurrence is f(n) = f(n-1) + f(n-2) (each path either ends with a 1-step from n-1 or a 2-step from n-2). Base cases: f(1) = 1, f(2) = 2. Initialize prev2 = 1, prev1 = 2. Loop from i = 3 to n: curr = prev1 + prev2; prev2 = prev1; prev1 = curr. Return prev1 (which equals n for n <= 2 — handle those as base cases). O(n) time, O(1) extra space. This is literally the Fibonacci recurrence offset by one index.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • fibonacci

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Adobe

Practice these live with InterviewChamp.AI

Drill Climbing Stairs and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →