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 Sam K., 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

More Dynamic Programming practice problems

See all Dynamic Programming problems →