Skip to main content

🟩 Climbing Stairs (#70)

🔗 Problem Link​

📋 Problem Statement​

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​

Example 1​

Input: n = 2
Output: 2
Explanation: 1+1, 2

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: This is Fibonacci! To reach step n, you can come from step n-1 or n-2.

Why DP?

  • dp[i] = dp[i-1] + dp[i-2]
  • O(n) time, O(1) space with optimization
  • Classic DP problem

Approaches:

  1. Recursive (exponential) - slow
  2. DP array: O(n) time, O(n) space
  3. DP optimized: O(n) time, O(1) space - optimal

Pattern: "Fibonacci DP" pattern.

🐍 Solution: Python​

Approach: Space-Optimized DP​

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

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

        prev2, prev1 = 1, 2

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

🔵 Solution: Golang​

Approach: O(1) Space​

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

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    prev2, prev1 := 1, 2

    for i := 3; i <= n; i++ {
        current := prev1 + prev2
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

📚 References​