Climbing Stairs Dynamic Programming: 5 Easy Wins for Newbies

Climbing Stairs is everyone's first DP problem. It's also where recursion habits go to die.

The naive code mirrors the story: ways(n) = ways(n-1) + ways(n-2). Clean, correct, catastrophic. It recomputes the same subproblems millions of times. At n = 40 it makes 100M+ calls. You'll watch it hang on a trivial input.

The fix is five lines bottom-up. Two rolling variables, one loop from 3 to n. That's O(n) time, O(1) space. Don't just memorize the loop — derive the recurrence from the last-step choice and you'll own every DP follow-up.

Counting Distinct Ways, Not Finding a Shortest Path

Given n stairs, count distinct ways to reach the top taking 1 or 2 steps at a time. Order matters: 1+2 and 2+1 are different ways. n = 2 gives 2 ([1,1], [2]); n = 3 gives 3 ([1,1,1], [1,2], [2,1]); n = 5 gives 8.

Constraints: 1 ≤ n ≤ 45. The cap exists because ways(45) = 1,836,311,903 fits 32-bit signed int — the problem is designed around Fibonacci growth. Return a count, not the paths (listing them would be exponential).

Walk n = 4 by last move: paths ending with a single arrive from step 3 (3 ways); paths ending with a double arrive from step 2 (2 ways). Total 5: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]. The last-move split is the whole derivation.

Naive Recursion Recomputes the Same Step 2^n Times

Naive recursion returns ways(n-1) + ways(n-2) directly. Correct, and O(2^n) time: ways(40) triggers ~200M calls because ways(k) is recomputed ~2^(n-k) times. Space is O(n) stack depth. At n = 45 (~2 billion calls) it never finishes; past n = 1000 it also hits Python's recursion limit.

The call tree shows the disease: ways(5) recomputes ways(3) three times and ways(2) five times. Exponential redundancy from overlapping subproblems — the textbook DP symptom.

Interview play: write the recurrence, name the overlap, and refuse to submit it. 'Naive recursion is O(2^n) on overlap — I'll build bottom-up.' That sentence is the DP password.

Bottom-Up DP: Each Step Is the Sum of the Previous Two

Classify all paths by their last move: from n-1 via single, or from n-2 via double. The classes are disjoint and exhaustive, so ways(n) = ways(n-1) + ways(n-2). Seeds: ways(1) = 1 ([1]), ways(2) = 2 ([1,1],[2]). Each state depends only on solved smaller states — compute from 3 upward, once each: O(n) time.

Proof sketch by induction: base seeds hold by enumeration. Assume all values below n correct; the last-move partition counts every n-path exactly once (each path has exactly one last move), so the sum is exact. Rolling variables keep only the two predecessors the recurrence reads: first, second = 1, 2, then per step nxt = first + second with a shift. Space drops from O(n) table to O(1) with identical results.

This is Fibonacci shifted by one index (ways(n) = Fib(n+1)) — but derive it live rather than quoting. Derivation beats recall in scoring.

The Bottom-Up DP Solution in Full Python

The code above is the complete LeetCode submission. Trace n = 5: guard skipped; (1,2) → step3: (2,3) → step4: (3,5) → step5: (5,8). Returns 8. Trace n = 1: guard returns 1. n = 2: guard returns 2.

Complexity: O(n) time (one loop), O(1) space (two ints). n = 45 returns 1836311903 instantly. No imports, no recursion, no tables.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        first, second = 1, 2
        for _ in range(3, n + 1):
            first, second = second, first + second
        return second

n = 1, n = 2 and Why the Base Cases Decide Everything

n = 1 returns 1, n = 2 returns 2 — the guard handles both. n = 45 (max) returns 1134903170 with no overflow in Python (mention 32-bit fit for Java/C++ follow-ups). Loop bounds range(3, n+1) execute zero times at n ≤ 2, but the guard already returned.

Tuple-assignment order matters: first, second = second, first + second evaluates the right side fully before rebinding. Sequential assignment (first = second; second = first + second) reuses the new first — the classic drift bug. Recursion variants need sys.setrecursionlimit past n = 1000; the loop has no such ceiling.

Why Two Variables Replace the Entire DP Table

Time O(n): one pass from 3 to n with O(1) per step. Space O(1): two integers regardless of n. Could O(log n) matrix exponentiation win? Asymptotically yes, practically no — for n ≤ 45 the loop is ~40 additions, clearer and already instant.

Whiteboard closer: 'Partition by last move, build bottom-up, keep two variables.' Then bridge: 'House Robber uses the same skeleton with a max instead of a sum; Min Cost Climbing Stairs adds per-step costs.' Two follow-ups answered before they're asked.