Climbing Stairs

easy
Dynamic ProgrammingDynamic ProgrammingMath

Given a staircase with n steps, determine the number of distinct ways you can climb to the top. Each time you can either climb 1 or 2 steps. Return the total number of distinct ways to reach step n from the ground.

Examples

Example 1

  • Input: n = 2
  • Output: 2
  • Explanation: There are two ways to climb to the top: 1 + 1 and 2.

Example 2

  • Input: n = 3
  • Output: 3
  • Explanation: There are three ways: 1 + 1 + 1, 1 + 2, and 2 + 1.

Constraints

  • 1 <= n <= 45

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

At each step we have two choices: take 1 step or take 2 steps. This naturally forms a recursive tree where climbStairs(n) = climbStairs(n-1) + climbStairs(n-2). The base cases are climbStairs(1) = 1 and climbStairs(2) = 2. While simple, this recurrence recomputes the same subproblems exponentially many times.

Algorithm

  1. If `n <= 2`, return `n` directly.
  2. Recursively compute the number of ways to reach step `n-1` and step `n-2`.
  3. Return the sum of those two values.
TimeO(2^n)SpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};
Java 21
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}
Python 3.12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
Go 1.26
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    return climbStairs(n-1) + climbStairs(n-2)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Instead of recomputing overlapping subproblems, we build the answer from the bottom up. We use a table where dp[i] represents the number of ways to reach step i. Since each step is reachable from the previous one or two steps, the recurrence is dp[i] = dp[i-1] + dp[i-2]. This is essentially computing the Fibonacci sequence.

Algorithm

  1. Create an array `dp` of size `n + 1`.
  2. Set `dp[1] = 1` and `dp[2] = 2`.
  3. For each step `i` from 3 to `n`, set `dp[i] = dp[i-1] + dp[i-2]`.
  4. Return `dp[n]`.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
Java 21
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
Python 3.12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]
Go 1.26
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
Approach 3

Space-Optimized DP

Intuition

Since each state only depends on the previous two states, we can reduce space to O(1) by maintaining just two variables instead of a full array. We iteratively update these variables as we step through from 3 to n.

Algorithm

  1. Handle base cases: if `n <= 2`, return `n`.
  2. Initialize `prev2 = 1` (ways to step 1) and `prev1 = 2` (ways to step 2).
  3. For each step from 3 to `n`, compute `current = prev1 + prev2`, then shift the variables.
  4. Return `prev1`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};
Java 21
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}
Python 3.12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        return prev1
Go 1.26
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        curr := prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

Frequently asked questions

What is the optimal time complexity of Climbing Stairs?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Climbing Stairs use?

Climbing Stairs is a easy-level Dynamic Programming problem involving Dynamic Programming, Math. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Climbing Stairs be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
n=
1
Expected Output
1