We can express this mathematically as: climb(n) = climb(n-1) + climb(n-2)

Pseudo-code:

text
function climb(n):
    if n == 1 return 1
    if n == 2 return 2
    return climb(n-1) + climb(n-2)

Time Complexity: $O(2^n)$ Analysis: This approach exhibits exponential time complexity because the recursion tree grows exponentially with n.

Why it fails: The brute force method fails due to Time Limit Exceeded (TLE) on larger inputs (e.g., $n = 45$). The algorithm redundantly recalculates the same subproblems many times. For instance, to calculate climb(5), it calculates climb(3) twice, climb(2) three times, and so on. This overlapping subproblem property indicates that pure recursion is inefficient.

Core Insight for Climbing Stairs

The critical intuition for the LeetCode 70 solution lies in the "optimal substructure" property. To arrive at step i, the immediate previous position must have been step i-1 (taking a single step) or step i-2 (taking a double step). There is no other way to reach step i.

Consequently, the total distinct ways to reach step i is the sum of the ways to reach step i-1 and the ways to reach step i-2. This establishes the recurrence relation: $dp[i] = dp[i-1] + dp[i-2]$

By computing these values iteratively from the bottom up (starting at step 1 and 2), we enforce the constraint that every future step is built upon valid previous configurations.

Visual Description: Visualize the solution as a linear array or a dependency graph. The value at index i is a sink node collecting flow from nodes i-1 and i-2. The computation moves strictly from left to right. We do not need to look back further than two indices, meaning the "window" of relevant state is constant size (2 elements) as it slides toward n.

Algorithm Strategy: DP - 1D Array (Fibonacci Style)

We implement the solution using an iterative bottom-up approach to avoid recursion depth issues and redundant calculations.

1. State Definition: Let dp[i] represent the number of distinct ways to reach step i.
2. Base Cases:
   • To reach step 1: 1 way (1 step).
   • To reach step 2: 2 ways (1+1 or 2).
3. Recurrence Relation: For all $i > 2$, dp[i] = dp[i-1] + dp[i-2].
4. Space Optimization: Since dp[i] only relies on the immediate two predecessors, we do not need to maintain an array of size n. We can use two variables to store the values of dp[i-1] and dp[i-2], updating them as we iterate. This reduces the space complexity from linear to constant.

Execution Flow

1. Handle Edge Cases: If n is 1, return 1.
2. Initialize State:
   • Set prev2 = 1 (representing ways to reach step 1).
   • Set prev1 = 2 (representing ways to reach step 2).
3. Iterate: Loop from i = 3 to n.
   • Calculate current = prev1 + prev2.
   • Shift the window: Update prev2 to hold the value of prev1.
   • Update prev1 to hold the value of current.
4. Return Result: After the loop completes, prev1 contains the number of ways to reach step n.

Proof of Correctness

The algorithm is correct by mathematical induction.

• Base Case: For $n=1$, output is 1. For $n=2$, output is 2. These are trivially correct.
• Inductive Step: Assume the algorithm correctly computes the number of ways for all steps $k < i$. The set of paths to step $i$ is the disjoint union of paths ending with a 1-step move (from $i-1$) and paths ending with a 2-step move (from $i-2$). By the inductive hypothesis, the counts for $i-1$ and $i-2$ are correct. Therefore, their sum equals the correct count for $i$.

Reference Implementation

C++ Solution for LeetCode 70

cpp
class Solution {
public:
    int climbStairs(int n) {
        // Base cases
        if (n <= 2) {
            return n;
        }
        
        // prev2 represents ways to reach (i-2)
        // prev1 represents ways to reach (i-1)
        int prev2 = 1; 
        int prev1 = 2;
        
        for (int i = 3; i <= n; ++i) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};

Java Solution for LeetCode 70

java
class Solution {
    public int climbStairs(int n) {
        // Base cases
        if (n <= 2) {
            return n;
        }
        
        // prev2 tracks step (i-2), prev1 tracks step (i-1)
        int prev2 = 1;
        int prev1 = 2;
        
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

Python Solution for LeetCode 70

python
class Solution:
    def climbStairs(self, n: int) -> int:
        # Base cases
        if n <= 2:
            return n
        
        # prev2 represents step (i-2)
        # prev1 represents step (i-1)
        prev2 = 1
        prev1 = 2
        
        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
            
        return prev1

Q: Why does my loop start from 3 instead of 0 or 1?

• Mistake: Incorrect loop boundaries or base case handling.
• Why: The recurrence relation requires two previous values ($i-1$ and $i-2$). Steps 1 and 2 are base cases that do not have two valid predecessors in the context of the problem constraints.
• Consequence: Index out of bounds errors or incorrect calculation for small $n$.

Q: Is it wrong to use an array dp[n+1]?

• Mistake: Using $O(n)$ space when $O(1)$ is possible.
• Why: While using an array is correct for logic, it ignores the property that we only ever need the last two values.
• Consequence: The solution is correct but not space-optimal, which may be a point of critique in senior-level interviews.