Untitled — Python Coding — Nerchuko Academy

Climbing Stairs

EASY

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

Example 3:

Input: n = 1
Output: 1
Explanation: 1. 1 step

Constraints:

1 <= n <= 45

Function Signature (Python):

class Solution:
    def climbStairs(self, n: int) -> int:
        # Your code here
        pass

Solution Explanation & Interview Strategy

The Goal: Imagine a staircase with n steps. You can climb either 1 step or 2 steps at a time. We need to find out how many different combinations of 1-step and 2-step moves can get you to the top (the n-th step).

To reach step 1: Only 1 way (1 step).
To reach step 2: Two ways (1 step + 1 step, OR 2 steps).
To reach step 3: Three ways (1+1+1, OR 1+2, OR 2+1).

Approach 1: Brute-Force Recursion (Illustrative)

Let climb(k) be the number of ways to reach step k. To reach step k, you must have come from either step k-1 (by taking a 1-step) or step k-2 (by taking a 2-step). So, climb(k) = climb(k-1) + climb(k-2). Base cases:

climb(0) = 1 (One way to be at the ground - do nothing. This helps the recurrence for climb(2)). Some define climb(1)=1, climb(2)=2.
climb(1) = 1 (One way: take 1 step from ground 0).
Or more directly: climb(1) = 1, climb(2) = 2.

This recursive approach calculates the same subproblems repeatedly (e.g., climb(3) is needed for climb(5) and climb(4)), leading to exponential time.

# Conceptual brute-force recursion, inefficient due to re-computation.
class Solution:
    def climbStairs_recursive_brute(self, n: int) -> int:
        if n == 0: return 1 # One way to reach step 0 (stay)
        if n == 1: return 1 # One way to reach step 1
        if n < 0: return 0   # Cannot reach negative steps

        # To reach step n, we could have come from n-1 (by taking 1 step)
        # or from n-2 (by taking 2 steps)
        return self.climbStairs_recursive_brute(n - 1) + \
               self.climbStairs_recursive_brute(n - 2)

Complexity Analysis (Brute-Force Recursion):

Time Complexity: O(2^N). Each call branches into two, similar to Fibonacci calculation without memoization.

Space Complexity: O(N) for the recursion call stack depth.

Approach 2: Dynamic Programming - Bottom-Up (Tabulation)

We can use an array dp where dp[i] stores the number of ways to reach step i.

dp[0] = 1 (One way to be at the start - take 0 steps).
dp[1] = 1 (One way to reach step 1: 0 -> 1).
For i from 2 to n: dp[i] = dp[i-1] + dp[i-2].

The final answer is dp[n].

class Solution:
    def climbStairs_dp_bottom_up(self, n: int) -> int:
        if n <= 0: return 0 # Or 1 if n=0 is considered a valid state (e.g. 1 way to stay)
        if n == 1: return 1
        if n == 2: return 2

        # dp[i] will store the number of ways to reach step i
        dp = [0] * (n + 1)
        dp[1] = 1 # 1 way to reach step 1
        dp[2] = 2 # 2 ways to reach step 2 (1+1 or 2)

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
            
        return dp[n]

Complexity Analysis (Bottom-Up DP):

Time Complexity: O(N). We iterate from 3 up to N once.

Space Complexity: O(N) for the dp array.

Approach 3: Dynamic Programming - Optimized Space (Constant Space)

Since dp[i] only depends on dp[i-1] and dp[i-2], we don't need to store the entire dp array. We only need to keep track of the previous two values, similar to how one can calculate Fibonacci numbers iteratively with constant space.

class Solution:
    def climbStairs_dp_optimized_space(self, n: int) -> int:
        if n <= 0: return 0
        if n == 1: return 1
        # For n=2, ways are (1,1) and (2) -> 2 ways
        # For n=3, ways are (1,1,1), (1,2), (2,1) -> 3 ways

        one_step_back = 2  # Corresponds to dp[2] or ways to reach step 2
        two_steps_back = 1 # Corresponds to dp[1] or ways to reach step 1
        
        # We need to calculate for steps 3 up to n
        for i in range(3, n + 1):
            current_ways = one_step_back + two_steps_back
            two_steps_back = one_step_back
            one_step_back = current_ways
            
        return one_step_back # After loop, one_step_back holds ways for step n

# Example Usage:
# sol = Solution()
# print(sol.climbStairs_dp_optimized_space(2)) # Output: 2
# print(sol.climbStairs_dp_optimized_space(3)) # Output: 3
# print(sol.climbStairs_dp_optimized_space(4)) # Output: 5

Complexity Analysis (DP with Optimized Space):

Time Complexity: O(N). We iterate from 3 up to N once.

Space Complexity: O(1). We only use a few variables to store the previous two results.

Approach 4: Recursion with Memoization (Top-Down DP)

This is the recursive approach with a cache (memo) to store results of subproblems already computed.

class Solution:
    def climbStairs_dp_top_down(self, n: int) -> int:
        memo = {} # Memoization cache

        def _climb(k: int) -> int:
            if k == 0: return 1 
            if k == 1: return 1
            # If n=2, result should be 2. Base cases for n=1, n=2 might be simpler.
            # Let's adjust base cases to match standard Fibonacci/problem examples:
            # ways(1) = 1, ways(2) = 2
            # This means _climb(k) should return ways to climb k steps
            # if k==1: return 1
            # if k==2: return 2
            # The above k=0, k=1 base cases are for a different DP state formulation.
            # Let's use the more direct problem mapping:
            
            if k <= 0: return 0 # Cannot climb negative or zero steps to reach a positive target initially
                                 # or more precisely:
            if k == 1: return 1  # 1 way to climb 1 step
            if k == 2: return 2  # 2 ways to climb 2 steps


            if k in memo:
                return memo[k]
            
            result = _climb(k - 1) + _climb(k - 2)
            memo[k] = result
            return result
        
        if n <= 0: return 0 # As per constraints or problem def
        return _climb(n)

Complexity Analysis (Top-Down DP with Memoization):

Time Complexity: O(N). Each state from 1 to N is computed once due to memoization.

Space Complexity: O(N) for the memoization cache and O(N) for the recursion call stack.

Key Takeaways for Interviews:

Recognize Fibonacci Pattern: The recurrence ways(n) = ways(n-1) + ways(n-2) is the hallmark of Fibonacci-like sequences.
Start with Recursion (Conceptually): Explain the recursive idea and its overlapping subproblems to motivate DP.
DP State and Recurrence: Clearly define dp[i] and the recurrence.
Base Cases: Correctly identify base cases (e.g., dp[1]=1, dp[2]=2 or dp[0]=1, dp[1]=1 depending on how you map to Fibonacci indices). The example solutions use dp[1]=1, dp[2]=2 for direct mapping to problem steps.
Bottom-Up vs. Top-Down: Be prepared to implement either. The bottom-up iterative approach is often preferred for its explicitness and avoidance of recursion depth limits.
Space Optimization: The constant space O(1) solution is an excellent optimization to discuss and implement, showing a deeper understanding.