Climbing Stairs

Concept

LeetCode #70.
Problem: 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?

Input: n = 3

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Output: 3

This is the quintessential introductory DP problem.
How do you know it’s DP? It asks for the “total number of ways”, and it involves making sequential choices (1 step or 2 steps).

The Mathematical Breakdown

Let’s say the staircase has 5 steps (n = 5).
You are trying to find the total number of ways to land exactly on Step 5.

If the rule says you can only jump 1 or 2 steps at a time, where could you possibly have been standing immediately prior to landing on Step 5?
You MUST have jumped from Step 4 (a 1-step jump), or you jumped from Step 3 (a 2-step jump). It is mathematically impossible to have arrived from anywhere else.

Therefore, the total number of ways to reach Step 5 is exactly:
Ways(5) = Ways(4) + Ways(3)

This is the exact Recurrence Relation of the Fibonacci sequence! dp[i] = dp[i-1] + dp[i-2].

Implementation (Tabulation)

We will use a dp Array to represent the staircase. dp[i] holds the total number of unique ways to reach step i.

// Time Complexity: O(N)
// Space Complexity: O(N)

function climbStairs(n: number): number {
    // Handle Base Cases early
    if (n === 1) return 1;
    if (n === 2) return 2;

    const dp = new Array(n + 1);
    
    // Base Cases
    dp[1] = 1; // Only 1 way to reach Step 1 (1)
    dp[2] = 2; // Two ways to reach Step 2 (1+1, or 2)

    // Build the staircase
    for (let i = 3; i <= n; i++) {
        // The core DP logic:
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

State Reduction ($O(1)$ Space)

Because our Recurrence Relation dp[i] = dp[i-1] + dp[i-2] only looks backwards exactly 2 steps, we do not need to keep the entire staircase in memory! We just need two pointers.

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

function climbStairsOptimized(n: number): number {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let twoBack = 1; // Represents dp[1]
    let oneBack = 2; // Represents dp[2]

    for (let i = 3; i <= n; i++) {
        const current = twoBack + oneBack;
        
        // Slide the window forward up the stairs
        twoBack = oneBack;
        oneBack = current;
    }

    return oneBack;
}

Interview Questions

Q: What if the problem changed the rules: “You can jump 1, 2, or 3 steps”?
A: The logic perfectly scales. The Recurrence Relation simply becomes:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
You would initialize 3 Base Cases (dp[1], dp[2], dp[3]), and the for loop would start at i=4.
If you used State Reduction, you would need 3 variables (threeBack, twoBack, oneBack).

Q: Can I solve this using Backtracking instead of DP?
A: If you write a Backtracking algorithm to simulate jumping every possible sequence of steps, you will physically map out the exact paths. This is required if the interviewer asks: “Return a list of all the physical paths” ([[1,1,1], [1,2]]). However, Backtracking takes exponential $O(2^N)$ time. Because this problem only asks for the number of ways, using Backtracking will trigger a Time Limit Exceeded error for any $N > 40$. You must use DP.