Climbing Stairs (LC 70)

Pattern: Dynamic Programming (Fibonacci recurrence)
Difficulty: Easy
Key Concept: Ways to reach step n equals ways to reach n-1 plus ways to reach n-2 (order matters).

Problem Statement

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 reach the top?

Input: Integer n — the number of steps to the top (1 <= n <= 45 on LeetCode).

Output: Integer — the number of distinct ways to reach the top.

Example: n = 3 → 3 (1+1+1, 1+2, 2+1).

1. Algorithm & Pseudocode

Idea: From step i, you could have arrived from step i-1 (single step) or step i-2 (double step). So:

ways(i) = ways(i-1) + ways(i-2) with base cases ways(1) = 1, ways(2) = 2 (or unify with ways(0) = 1 as “one way to stand on the ground”).

Brute force (recursive)

function climb(n):
    if n <= 2: return n   // or handle n==1, n==2 explicitly
    return climb(n-1) + climb(n-2)

Memoized

memo = array size n+1, filled with -1
function climb(n):
    if n <= 2: return n
    if memo[n] != -1: return memo[n]
    memo[n] = climb(n-1) + climb(n-2)
    return memo[n]

Optimal (O(1) space)

if n <= 2: return n
prev2 = 1   // ways to reach step 1
prev1 = 2   // ways to reach step 2
for i from 3 to n:
    curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
return prev1

2. Step-by-Step Analysis (Beginner-Friendly)

Why add ways(n-1) and ways(n-2)?
Your last move is either a 1-step from n-1 or a 2-step from n-2. Those sets of paths do not overlap (different last move), and every valid path ends one of those two ways. So you count both.
Why is brute force O(2^n)?
Without caching, each call splits into two calls. The recursion tree grows like a binary tree whose depth is about n, so the number of nodes is exponential.
Why does memoization fix the time?
There are only n distinct subproblems (climb(1) … climb(n)). Each is computed once; filling the memo turns exponential work into linear.
Why can we use only two variables?
To compute the next value you only need the previous two. Older values are never read again—classic Fibonacci rolling state.
Why n <= 2 base cases?
For n = 1, only one way. For n = 2, two ways (1+1 or 2). The loop version seeds these as prev2 = 1, prev1 = 2.

3. The Dry Run

Sample: n = 5 (space-optimized iterative).

Interpretation: prev2 = ways to reach the step “two back” in the iteration, prev1 = ways to reach the step “one back,” curr = ways for current step index i.

Step `i`	`prev2` (before)	`prev1` (before)	`curr = prev1 + prev2`	`prev2` (after)	`prev1` (after)
init	—	—	—	1	2
3	1	2	3	2	3
4	2	3	5	3	5
5	3	5	8	5	8

Answer: 8 ways for n = 5.

Manual check: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 2+2+1, 2+1+2, 1+2+2 → eight sequences.

4. Java Solution

Brute Force

Recursive exploration without cache. Time: O(2^n). Space: O(n) call stack.

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Optimal

Memoized (top-down) — Time: O(n), Space: O(n) for memo + O(n) stack.

import java.util.Arrays;

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        memo[1] = 1;
        memo[2] = 2;
        return dfs(n, memo);
    }

    private int dfs(int n, int[] memo) {
        if (memo[n] != -1) {
            return memo[n];
        }
        memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
        return memo[n];
    }
}

Bottom-up O(1) extra space — Time: O(n), Space: O(1).

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int prev2 = 1;
        int prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

5. The “Java vs. Others” Edge

No tuple unpacking: In Python you might write a, b = b, a + b. In Java you need a temporary int curr (or prev1 + prev2 then shift)—same logic, slightly more lines.
Arrays.fill(memo, -1): Idiomatic way to mark “uncomputed” for int memo tables; avoids a manual loop.
LeetCode constraints: n <= 45 fits in int. For very large n, Fibonacci numbers overflow int/long; you would use BigInteger and a different problem statement.
Base cases: Keeping if (n <= 2) return n matches the usual counting for this problem (1 and 2 steps).

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(2^n)	O(n) stack	Recomputes same subproblems endlessly
Memoized	O(n)	O(n)	`Arrays.fill` + array cache; stack depth O(n)
Optimal (iterative O(1))	O(n)	O(1)	Two variables; same recurrence as Fibonacci