Problem statement

You are climbing a staircase with n steps. Each move climbs either 1 or 2 steps. In how many distinct ways can you reach the top?

Example 1

Input: n = 2
Output: 2
Explanation: 1+1 or 2.

Example 2

Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, or 2+1.

Constraints

• 1 <= n <= 45

Hints for Climbing Stairs

1. Hint 1

   Ways to reach step n = ways(n-1) + ways(n-2).

2. Hint 2

   That's the Fibonacci sequence — two rolling variables suffice.

How to solve Climbing Stairs

The last move onto step n was either a 1-step from n-1 or a 2-step from n-2, and those two families of routes are disjoint and cover everything. So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence, seeded with one way to stand at the bottom.

Approach

1. There is 1 way to be at step 0 (do nothing) and 1 way to reach step 1.
2. For each subsequent step, add the two previous counts.
3. Only the last two values are ever needed, so keep two variables instead of an array.
4. Return the count for step n.

Why it works

Every route to step n ends with exactly one final move, of size 1 or 2. Classifying routes by that final move partitions them into two groups with no overlap and nothing left out, and each group is in bijection with the routes to the step it came from. That is precisely the recurrence, and the two base cases pin it down.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The base case is 1 way to reach step 0, not 0 — otherwise every later count collapses.
• Naive recursion without memoisation is exponential and times out well before n = 45.
• At n = 45 the answer is over 1.8 billion — close to the 32-bit limit, so a narrower type would overflow.
• Update the two rolling variables in the right order, or you fold a value into itself.

Reference solution

Python

def climbStairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Java

public static int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

C++

int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

JavaScript

var climbStairs = function(n) {
    let a = 1, b = 1;
    for (let i = 2; i <= n; i++) {
        const c = a + b;
        a = b;
        b = c;
    }
    return b;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy