70. Climbing Stairs

Intuition

At any step, you can climb either 1 step or 2 steps. So, the number of ways to reach step n is the sum of:

• The number of ways to reach step n - 1 (and then take 1 step)

• The number of ways to reach step n - 2 (and then take 2 steps)

This is structurally identical to the Fibonacci sequence.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(n)$

Code

// Memoization array to cache results
int[] memo;

// Recursive helper function to count ways to climb to step n
int countWays(int step) {
    // Base case: only 1 way to reach the first step
    if (step == 1) return 1;

    // Base case: two ways to reach the second step (1+1 or 2)
    if (step == 2) return 2;

    // Return cached result if already computed
    if (memo[step] != -1) return memo[step];

    // Compute the result recursively and store it
    memo[step] = countWays(step - 1) + countWays(step - 2);

    return memo[step];
}

public int climbStairs(int n) {
    // Initialize memo array with -1 to indicate uncomputed values
    memo = new int[46];
    Arrays.fill(memo, -1);

    // Compute and return the number of ways to climb n stairs
    return countWays(n);
}