Climbing Stairs

Easy10–15 min

Topics

Dynamic ProgrammingMath

Companies

AmazonAdobeApple

Given a staircase of n steps, and the freedom to climb either 1 or 2 steps at a time, find how many distinct ways there are to reach the top. Every way of reaching a given step ends in exactly one of two moves: the last move was a single step from the step just below, or a double step from two steps below. That means the number of ways to reach any step is simply the sum of the ways to reach the two steps before it — the same idea behind the Fibonacci sequence, just counting climbing paths instead of numbers. Starting from the two easy base cases (there's exactly 1 way to be standing on step 1, and 2 ways to be standing on step 2) and sweeping upward, each step's count can be built from the two counts that came immediately before it.

Test Case 1:

Input:n = 4

Output:5

Explanation:1+1+1+1, 1+1+2, 1+2+1, 2+1+1, or 2+2 — 5 distinct ways to arrange single and double steps that sum to 4.

Test Case 2:

Input:n = 6

Output:13

Explanation:The count follows a Fibonacci-style pattern: ways(6) = ways(5) + ways(4) = 8 + 5 = 13.

Test Case 3:

Input:n = 5

Output:8

Explanation:The count follows a Fibonacci-style pattern: ways(5) = ways(4) + ways(3) = 5 + 3 = 8.

Constraints

◆1 ≤ n ≤ 30

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Standing on step i, the top can be reached either by taking a single step to i+1 or a double step to i+2 — so the number of ways to finish from step i is just the number of ways from i+1 plus the number of ways from i+2. Landing exactly on step n counts as one complete way to finish, and overshooting past n contributes nothing. Starting that recursion at step 0 and letting it branch all the way to the top answers the question, but the same step gets recomputed from scratch every time a different earlier decision happens to land back on it.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int n;

    public int climbStairs(int n) {
        this.n = n;
        return solve(0);
    }

    private int solve(int i) {
        if (i == n) return 1;
        if (i > n) return 0;
        return solve(i + 1) + solve(i + 2);
    }
}

Optimal — Bottom-Up with O(1) Space

Optimal

Instead of asking "how many ways to finish from step i", flip the question around to "how many ways to arrive at step i from the bottom" — the count for step i is just the count for step i-1 plus the count for step i-2, since the last move taken to land on i was either a single step or a double step. Only the two most recent counts are ever needed to compute the next one, so there's no need to keep a whole array — two running variables, updated as the steps are swept from the bottom to the top, are enough.

TimeO(n)

SpaceO(1)