Climbing Stairs

easyTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Ways to reach step `i` equals `dp[i-1] + dp[i-2]` (arrive via 1-step or 2-step hop). Collapse the DP table to two rolling scalar variables `prev, curr`.

2. Complexity Bounds & Proof

N constant-time Fibonacci additions in O(1) space.

3. Minimal Idiomatic Code

def climbStairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

4. Failure Modes & Interview Follow-ups

Pitfalls:- Off-by-one between `n=1 -> 1` and `n=2 -> 2` (`fib(n+1)`). - Exponential `O(2^N)` recursive branching without memoization.
Follow-ups:- Min Cost Climbing Stairs adds `cost[i]` weight per step; Matrix Exponentiation computes Nth term in O(log N) for huge N.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

House Robber (O(N))Decode Ways (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.