Climbing Stairs

Difficulty: Easy | Acceptance: 54.10% | Paid: No Topics: Math, Dynamic Programming, Memoization

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?

• Examples
• Constraints
• Brute Force Recursion
• Recursion with Memoization
• Dynamic Programming
• Space Optimized DP
• Matrix Exponentiation
• Binet’s Formula

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: 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

Brute Force Recursion

Intuition At each step, we have two choices: take 1 step or take 2 steps. We recursively explore both paths and sum the results.

Steps

• Base case: if n is 1 or 2, return n (only 1 way for 1 step, 2 ways for 2 steps)
• Recursive case: return climbStairs(n-1) + climbStairs(n-2)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

Complexity

• Time: O(2ⁿ) - exponential due to repeated subproblems
• Space: O(n) - recursion stack depth
• Notes: Simple but inefficient for larger n due to redundant calculations

Recursion with Memoization

Intuition Store computed results to avoid redundant calculations. Each subproblem is solved only once.

Steps

• Create a memoization structure (array/hashmap)
• Before computing, check if result exists in memo
• After computing, store result in memo before returning

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}
        
        def dfs(k):
            if k <= 2:
                return k
            if k in memo:
                return memo[k]
            memo[k] = dfs(k - 1) + dfs(k - 2)
            return memo[k]
        
        return dfs(n)

Complexity

• Time: O(n) - each subproblem computed once
• Space: O(n) - memo array + recursion stack
• Notes: Top-down DP approach, eliminates redundant work

Dynamic Programming

Intuition Build solution bottom-up. Each step’s ways depend only on the previous two steps.

Steps

• Initialize dp array with base cases: dp[1] = 1, dp[2] = 2
• Iterate from 3 to n, computing dp[i] = dp[i-1] + dp[i-2]
• Return dp[n]

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]

Complexity

• Time: O(n) - single pass through all steps
• Space: O(n) - dp array stores all intermediate results
• Notes: Bottom-up DP, intuitive and easy to understand

Space Optimized DP

Intuition Only the last two values are needed to compute the next one. Eliminate the array entirely.

Steps

• Handle base cases directly
• Maintain two variables for previous two results
• Update variables iteratively, shifting values forward

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev1 = 1
        prev2 = 2
        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev1 = prev2
            prev2 = curr
        return prev2

Complexity

• Time: O(n) - single pass through all steps
• Space: O(1) - only two variables used
• Notes: Optimal for this problem, most commonly used in interviews

Matrix Exponentiation

Intuition The recurrence relation can be represented as matrix multiplication. Using fast exponentiation, we compute the result in logarithmic time.

Steps

• Represent the recurrence as [[1,1],[1,0]] matrix
• Use binary exponentiation to raise matrix to power n
• Extract result from matrix[0][0]

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        def multiply(a, b):
            return [
                [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
                [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
            ]
        
        def power(matrix, exp):
            result = [[1, 0], [0, 1]]
            while exp > 0:
                if exp % 2 == 1:
                    result = multiply(result, matrix)
                matrix = multiply(matrix, matrix)
                exp //= 2
            return result
        
        base = [[1, 1], [1, 0]]
        result = power(base, n)
        return result[0][0]

Complexity

• Time: O(log n) - binary exponentiation halves exponent each step
• Space: O(1) - constant space for matrix operations
• Notes: Overkill for n ≤ 45, but useful for very large n constraints

Binet’s Formula

Intuition Fibonacci numbers have a closed-form solution using the golden ratio. Direct computation yields O(1) time.

Steps

• Calculate golden ratio φ = (1 + √5) / 2
• Apply Binet’s formula: result = round(φ^(n+1) / √5)
• Return the rounded integer

class Solution:
    def climbStairs(self, n: int) -> int:
        import math
        sqrt5 = math.sqrt(5)
        phi = (1 + sqrt5) / 2
        psi = (1 - sqrt5) / 2
        return int(round((phi ** (n + 1) - psi ** (n + 1)) / sqrt5))

Complexity

• Time: O(1) - constant time arithmetic operations
• Space: O(1) - no additional storage
• Notes: Elegant mathematical solution, but floating-point precision issues for very large n