Climbing Stairs

LeetCode 70: Climbing Stairs Solution & Explanation

Problem Overview

TL;DR: The number of distinct ways to reach step n is the sum of the ways to reach step n-1 and step n-2, following the Fibonacci sequence logic.

The Climbing Stairs problem asks us to determine the total number of distinct ways to reach the top of a staircase with n steps. At any given point, you are allowed to climb either 1 or 2 steps. This is a fundamental problem in algorithmic interviews, serving as the standard introduction to dynamic programming. The LeetCode 70 solution requires identifying that the problem can be broken down into smaller, overlapping subproblems.

Brute Force Approach for Climbing Stairs

A naive approach attempts to simulate every possible combination of steps using recursion. To define the number of ways to reach step n, denoted as climb(n), we observe that the final move must have been either a 1-step jump from n-1 or a 2-step jump from n-2.

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

Pseudo-code:

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.

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$.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern used in Climbing Stairs is directly applicable to several other popular interview questions. Understanding this core logic allows you to solve:

• LeetCode 91: Decode Ways: Similar to climbing stairs, but the transition depends on whether 1 or 2 digits form a valid character code.
• LeetCode 198: House Robber: Uses the same look-back logic ($i-1$ vs $i-2$), but involves a maximization decision rather than summation.
• LeetCode 213: House Robber II: Applies the House Robber logic on a circular array.
• LeetCode 337: House Robber III: Extends the pattern to tree structures.

Reference Implementation

C++ Solution for LeetCode 70

1class Solution {
2public:
3    int climbStairs(int n) {
4        // Base cases
5        if (n <= 2) {
6            return n;
7        }
8        
9        // prev2 represents ways to reach (i-2)
10        // prev1 represents ways to reach (i-1)
11        int prev2 = 1; 
12        int prev1 = 2;
13        
14        for (int i = 3; i <= n; ++i) {
15            int current = prev1 + prev2;
16            prev2 = prev1;
17            prev1 = current;
18        }
19        
20        return prev1;
21    }
22};

Java Solution for LeetCode 70

1class Solution {
2    public int climbStairs(int n) {
3        // Base cases
4        if (n <= 2) {
5            return n;
6        }
7        
8        // prev2 tracks step (i-2), prev1 tracks step (i-1)
9        int prev2 = 1;
10        int prev1 = 2;
11        
12        for (int i = 3; i <= n; i++) {
13            int current = prev1 + prev2;
14            prev2 = prev1;
15            prev1 = current;
16        }
17        
18        return prev1;
19    }
20}

Python Solution for LeetCode 70

1class Solution:
2    def climbStairs(self, n: int) -> int:
3        # Base cases
4        if n <= 2:
5            return n
6        
7        # prev2 represents step (i-2)
8        # prev1 represents step (i-1)
9        prev2 = 1
10        prev1 = 2
11        
12        for i in range(3, n + 1):
13            current = prev1 + prev2
14            prev2 = prev1
15            prev1 = current
16            
17        return prev1