Framework Thinking - Neetcode 150 - Count Ways of Climbing Stairs

Here is solutions for Climbing Stairs.

1. Understand the problem

You are standing at the bottom of a staircase with n steps.
Each time, you can climb:
- 1 step, or
- 2 steps
Your task is to return the total number of distinct ways to reach step n.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1.What is the range of n?

LeetCode: 1 ≤ n ≤ 45

Can n = 0?

Usually no in LeetCode, but mathematically it would be 1 way (do nothing).

Are we allowed to take jumps larger than 2?

❌ No, only {1, 2}.

Do different orders count as different ways?

✅ Yes. (1+2 and 2+1 are different)

Do we need the actual paths or just the count?

✅ Only the count.

3. Explore examples.

Example 1

n = 1
Ways: [1]
Output = 1

Example 2

n = 2
Ways: [1+1], [2]
Output = 2

Example 3

n = 3
Ways:
1 + 1 + 1
1 + 2
2 + 1
Output = 3

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Naive Recursion (Exponential) - Time O(2^N), Space O(N)

f(n) = f(n-1) + f(n-2)

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n-1) + climbStairs(n-2)

Time: O(2^N)
Space: O(N)

4.2. Solution 2: Precomputed DP - Time O(N), Space O(N)

dp[i] = number of ways to reach step i
dp[i] = dp[i-1] + dp[i-2]

Time: O(N)
Space: O(N)

4.3. Space-Optimized DP - Using only prev1, prev2 - Time O(N), Space O(1)

def climbStairs(n):
    if n <= 2:
        return n

    prev2 = 1   # dp[1]
    prev1 = 2   # dp[2]

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

    return prev1

Time: O(N)
Space: O(1)

5. Implement solutions.

5.1. Recursion - Time O(2^N), Space O(N)

class Solution:
    def climbStairs(self, n: int) -> int:

        def dfs(i):
            if i >= n:
                return i == n
            return dfs(i + 1) + dfs(i + 2)

        return dfs(0)

Time: O(2^N)
Space: O(N)

5.2. Caching DP - Top-down - Time O(N), Space O(N)

class Solution:
    def climbStairs(self, n: int) -> int:
        cache = [-1] * n
        def dfs(i):
            if i >= n:
                return i == n
            if cache[i] != -1:
                return cache[i]
            cache[i] = dfs(i + 1) + dfs(i + 2)
            return cache[i]

        return dfs(0)

Time: O(N)
Space: O(N)

5.3. Bottom-up DP - Build O(N) from Index 0 - Time O(N), Space O(N)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Time: O(N)
Space: O(N)

5.4. Dynamic Programming (Space Optimized) - Time O(N), Space O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1

        for i in range(n - 1):
            temp = one
            one = one + two
            two = temp

        return one

Time: O(N)
Space: O(1)

5.5. Math - Time O(1), Space O(1)

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

Time: O(1)
Space: O(1)

6. Dry run testcases.

prev2 = 1   # ways to reach step 1
prev1 = 2   # ways to reach step 2
cur = prev1 + prev2
cur = 3 + 2 = 5

December 6, 2025