How do you approach Climbing Stairs?

Think about the last step: you either came from step n-1 or step n-2.

What is the time complexity of Climbing Stairs?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Climbing Stairs?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Climbing Stairs

EasyAlgorithms

Description

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?

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: There are three ways to climb to the top: 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

Constraints

- 1 <= n <= 45

Climbing Stairs: approach, complexity and pitfalls

An easy dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Think about the last step: you either came from step n-1 or step n-2.
This means ways(n) = ways(n-1) + ways(n-2).
This is the Fibonacci sequence!

The optimal approach

Show the approach: Dynamic Programming (Fibonacci)

The number of ways to reach step n is the sum of ways to reach step n-1 and n-2, which is the Fibonacci sequence.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.