Climbing Stairs

EASY✓ CHIP-TIMEDLC #70 — FULL STATEMENT ↗

The drill: Count the distinct ways to climb n steps taking 1 or 2 at a time. The count explodes fast — the real question is about overlapping subproblems.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A staircase has n steps, and each stride up it covers either one step or two. The task is to count how many distinct sequences of strides reach exactly the top.

Two sequences count as different the moment their stride pattern differs anywhere — a 1-then-2 climb and a 2-then-1 climb over the same three steps are two separate ways, not one.

The answer is a single count of all such distinct stride sequences for the staircase's height.

EX 01

n = 1

→ 1

EX 02

n = 2

→ 2

EX 03

n = 3

→ 3

n is a small positive integer, at most a few dozen
each stride covers exactly one or two steps
order of strides matters — different orders count separately
answer fits comfortably in a standard integer

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The last move was a single or a double. What does that make the count for n?

HINT 2 THE STRUCTURE

ways(n) = ways(n−1) + ways(n−2) — Fibonacci in a tracksuit. Naive recursion recomputes the same values exponentially often.

HINT 3 ONE STEP FROM THE ANSWER

Two rolling variables and one pass up to n. No array, no recursion.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ROLLING STAIRCASEPATTERN · ROLLING FIBn = 5

ROLLING WAYS COUNT

ways(1) → 1

ways(0) → 1

STEP 1

Climbing 5 stairs, 1 or 2 steps at a time. ways(1)=1 and ways(0)=1 seed two rolling variables — no array needed at all.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/climbing-stairs.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def climbStairs(self, n: int) -> int:
        one_back, two_back = 1, 1
        for _ in range(n - 1):
            one_back, two_back = one_back + two_back, one_back
        return one_back

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 6 LN

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 5 LN

class Solution {
    public int climbStairs(int n) {
        int oneBack = 1;
        int twoBack = 1;
        for (int i = 0; i < n - 1; i++) {
            int next = oneBack + twoBack;
            twoBack = oneBack;
            oneBack = next;
        }
        return oneBack;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 12 LN

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

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 8 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED