leetcode-textbook

0070 - Climbing Stairs

Difficulty: Easy Pattern: 1-D DP LeetCode: https://leetcode.com/problems/climbing-stairs/

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. Return the number of distinct ways you can climb to the top.

Signature:

int climbStairs(int n)

Examples (verbatim from LeetCode):

Input:  n = 2
Output: 2
Explanation: 1+1 or 2.

Input:  n = 3
Output: 3
Explanation: 1+1+1, 1+2, or 2+1.

Constraints: 1 <= n <= 45.

Intuition

This is the gateway DP problem — the trigger phrases are “how many ways” and “answer for n depends on smaller n”.

Ask: what was the last move that landed me on step n? It was either a 1-step move from step n-1, or a 2-step move from step n-2. Every way to reach n ends in exactly one of those two moves, and the two cases do not overlap. So:

ways(n) = ways(n-1) + ways(n-2)

That is exactly the Fibonacci recurrence. The base cases are direct: ways(1) = 1 (one single step) and ways(2) = 2 (1+1 or 2).

A naive recursion recomputes ways(2) and ways(1) over and over — exponential time. We cache each ways(i) once, left to right, in O(n) time. Because the recurrence only looks back two steps, two variables are enough instead of a whole array.

Checkpoint A – The Fibonacci recurrence

Pause and answer before expanding. Wrong guesses teach more than fast right ones.

Q1 (recall). What is the recurrence for ways(n), the number of distinct ways to reach step n?

Show answer **(b)** -- your last move onto step n came from n-1 (one step) or n-2 (two steps), so the two counts add.

Q2 (comprehend). What base cases does the code rely on?

Show answer **(b)** -- the line `if (n <= 2) return n` folds ways(1)=1 and ways(2)=2; these are the smallest cases you can count directly.

Pseudocode

function climbStairs(n):
    if n is 1: return 1
    if n is 2: return 2

    # prev2 = ways(i-2), prev1 = ways(i-1)
    prev2 = 1            # ways(1)
    prev1 = 2            # ways(2)
    for i from 3 to n:
        current = prev1 + prev2     # ways(i) = ways(i-1) + ways(i-2)
        prev2 = prev1
        prev1 = current
    return prev1

The state is just (prev2, prev1) — a 2-element window that slides rightward. We return prev1 because after the last update it holds ways(n).

Java Solution

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

if (n <= 2) return n folds the two base cases into one check (ways(1) = 1, ways(2) = 2). The loop invariant is “after iteration i, prev1 = ways(i) and prev2 = ways(i-1)”. We update prev2 before prev1 so neither old value is lost. With n <= 45 the largest result (1,836,311,903) fits in int; beyond n=46 it would overflow and you would need long.

Complexity

Time:  O(n)   -- one loop, n-2 iterations, constant work each.
Space: O(1)   -- only two rolling variables; no dp array.

Dry-Run

Step-by-step on n = 5:

i prev2 (ways(i-2)) prev1 (ways(i-1)) current = prev1 + prev2 meaning
- 1 2 - init: ways(1)=1, ways(2)=2
3 1 2 3 ways(3) = 3
4 2 3 5 ways(4) = 5
5 3 5 8 ways(5) = 8

After the loop, prev1 = 8 = ways(5). Verification by enumeration: the 8 ways to climb 5 stairs are 11111, 1112, 1121, 1211, 2111, 122, 212, 221.

Checkpoint B – Trace the staircase

Q1 (apply). Trace n = 4. (Recall ways(1)=1, ways(2)=2, ways(3)=3.) What does climbStairs(4) return?

Show answer **(c)** -- ways(4) = ways(3) + ways(2) = 3 + 2 = 5. The loop sets current=3 at i=3, then current=5 at i=4, leaving prev1=5.

Q2 (analyze). What breaks if you swap the two update lines (prev1 = current before prev2 = prev1)?

Show answer **(b)** -- prev2 must grab the OLD prev1 before prev1 is overwritten; reversing the order makes prev2 equal current, losing ways(i-2).

Q3 (transfer). Suppose you may climb 1, 2, or 3 steps at a time. In one sentence, how would the recurrence change?

Show answer It becomes ways(n) = ways(n-1) + ways(n-2) + ways(n-3): sum the counts from the three possible last moves, keeping three rolling variables and adding a base case ways(3).

Common mistakes