99.Climbing Stairs

Intuition

Stand on step i. To get here you must have come from i - 1 (one step) or i - 2 (two steps). Count the ways to reach each of those and add them. Recurse until you hit the base cases.

Recurrence: f(i) = f(i - 1) + f(i - 2), with f(0) = 1 (one way to stand still at the bottom) and f(1) = 1.

Algorithm

1. If n <= 1, return 1.
2. Otherwise return climbStairs(n - 1) + climbStairs(n - 2).

Visualization

The recursion tree for n = 5. Notice f(3) is computed twice and f(2) three times — that duplicated work is what makes this exponential.

Code

class Solution {
    public int climbStairs(int n) {
        // base cases: one way to be at step 0 or step 1
        if (n <= 1) {
            return 1;
        }
        // last move was either a 1-step or a 2-step
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Complexity

• Time: O(2ⁿ) — each call branches into two (more precisely O(φⁿ) ≈ O(1.618ⁿ)); n = 45 will time out.
• Space: O(n) — maximum recursion depth.

Intuition

f(i) depends only on i, so its answer never changes. Store it the first time it is computed in memo[i] and return the stored value on every later call. Each of the n + 1 subproblems is now solved exactly once.

Algorithm

1. Create memo of size n + 1, filled with 0 (meaning "not computed" — every real answer is ≥ 1).
2. dfs(i): if i <= 1 return 1; if memo[i] != 0 return it.
3. Otherwise set memo[i] = dfs(i - 1) + dfs(i - 2) and return it.
4. Return dfs(n).

Dry Run

n = 5
dfs(5) → dfs(4) → dfs(3) → dfs(2) → dfs(1)=1, dfs(0)=1 → memo[2]=2
                          dfs(3) = memo[2] + dfs(1) = 2 + 1 → memo[3]=3
                 dfs(4) = memo[3] + memo[2] (cache hit) = 5 → memo[4]=5
        dfs(5) = memo[4] + memo[3] (cache hit) = 8

Code

class Solution {
    private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return dfs(n);
    }

    private int dfs(int i) {
        if (i <= 1) {
            return 1;
        }
        if (memo[i] != 0) {
            return memo[i]; // already solved
        }
        memo[i] = dfs(i - 1) + dfs(i - 2);
        return memo[i];
    }
}

Complexity

• Time: O(n) — each i from 2..n is computed once with O(1) work.
• Space: O(n) — memo array plus O(n) recursion stack.

Intuition

Instead of recursing from the top, fill the answers in increasing order of i. By the time we compute dp[i], both dp[i - 1] and dp[i - 2] are already known. No recursion, no stack.

Algorithm

1. Create dp of size n + 1; set dp[0] = 1, dp[1] = 1.
2. For i from 2 to n: dp[i] = dp[i - 1] + dp[i - 2].
3. Return dp[n].

Dry Run

n = 5:

dp[4] = dp[3] + dp[2] = 3 + 2 = 5, dp[5] = dp[4] + dp[3] = 5 + 3 = 8.

Code

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1; // standing at the ground
        dp[1] = 1; // a single 1-step
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Complexity

• Time: O(n) — one pass over the table.
• Space: O(n) — the dp array.

Intuition

The tabulation loop only ever reads the last two entries. Keep them in two variables, prev2 = f(i - 2) and prev1 = f(i - 1), and slide them forward each step.

Algorithm

1. prev2 = 1 (f(0)), prev1 = 1 (f(1)).
2. For i from 2 to n:
   • curr = prev1 + prev2
   • prev2 = prev1, prev1 = curr
3. Return prev1.

Dry Run

Code

class Solution {
    public int climbStairs(int n) {
        int prev2 = 1; // ways to reach step i - 2
        int prev1 = 1; // ways to reach step i - 1
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1; // for n = 1 the loop never runs and we return 1
    }
}

Complexity

• Time: O(n) — single loop.
• Space: O(1) — two integers.