Climbing Stairs LeetCode 70 Deep Dive

LeetCode 70 — Climbing Stairs — is one of the most famous introductory problems in dynamic programming. You are standing at the bottom of a staircase with n steps. On each move, you can climb either 1 step or 2 steps. The question is: in how many distinct ways can you reach the top?

This problem is deceptively simple — it looks like a straightforward combinatorics puzzle, but the right way to think about it is through DP. The key insight is that the number of ways to reach step n depends only on the ways to reach step n-1 (take 1 step) and step n-2 (take 2 steps). That gives a recurrence identical to Fibonacci.

LeetCode 70 is tagged Medium but is widely considered an Easy-level entry point into DP. It is often the first DP problem interviewers assign to warm up, and it serves as the foundation for Min Cost Climbing Stairs (LC 746), House Robber (LC 198), and Decode Ways (LC 91). If you can see why the recurrence works and how to optimize space to O(1), you have unlocked the linear DP pattern.

The number of ways to reach step n is: ways(n) = ways(n-1) + ways(n-2). The logic is direct — to stand at step n, you either stepped from n-1 (one step) or from n-2 (two steps). Every path to step n must have come from one of exactly those two places, so the total is their sum.

This recurrence is the Fibonacci sequence with different base cases. Fibonacci has fib(1) = 1, fib(2) = 1, fib(3) = 2. Climbing Stairs has ways(1) = 1, ways(2) = 2, ways(3) = 3. Climbing Stairs is Fibonacci shifted by one index: ways(n) = fib(n+1) where fib(1) = 1, fib(2) = 1. Recognizing this connection lets you write the O(1) space solution immediately.

Understanding why the recurrence holds is the core skill. It is not enough to memorize "this is Fibonacci." The reasoning — you came from n-1 or n-2, the two cases are mutually exclusive and exhaustive, so you add them — is the same reasoning that will unlock House Robber, Decode Ways, and every other linear DP problem you encounter.

The top-down approach defines a recursive function climb(n) with a memo cache. If memo[n] already exists, return it immediately. Otherwise compute memo[n] = climb(n-1) + climb(n-2). Base cases: climb(1) = 1 (one way to climb one step) and climb(2) = 2 (either take two singles or one double). Without memoization, naive recursion has exponential time O(2^n) because climb(n-2) is recomputed in every branch.

With memoization, each distinct value of n is computed exactly once and stored. The recursion tree collapses to a linear chain of length n. Time is O(n), space is O(n) for the memo plus O(n) for the call stack. Python makes this trivial with @lru_cache(maxsize=None) or functools.cache above the function — the decorator handles the cache transparently.

Top-down memoization is often the easiest approach to arrive at naturally because it follows the problem definition directly. You ask "how many ways to climb n?" and define it recursively. The memo just prevents redundant work. The main downside compared to bottom-up is recursion depth: for n close to 45 (the constraint limit) Python handles it fine, but in languages with small default stack sizes you may need to be careful.

The bottom-up approach builds a dp array from index 1 to n. Set dp[1] = 1 and dp[2] = 2. For each index i from 3 to n, compute dp[i] = dp[i-1] + dp[i-2]. Return dp[n]. This fills the table iteratively, never uses the call stack, and has O(n) time and O(n) space. It is the most explicit, readable form of the solution.

Python: def climbStairs(n): if n <= 2: return n; dp = [0] * (n+1); dp[1] = 1; dp[2] = 2; for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]; return dp[n]. Java: int[] dp = new int[n+1]; dp[1] = 1; if (n >= 2) dp[2] = 2; for (int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; return dp[n]. Both are clean and easy to debug — print the dp array to verify correctness before optimizing.

Bottom-up DP is usually the preferred solution to present in interviews because it is easy to read, reason about, and extends naturally to harder DP variants. Once you have the array solution working, the O(1) optimization is a mechanical step. The two-step process — array first, rolling variables second — demonstrates algorithmic maturity and structured thinking.

Since dp[i] only depends on dp[i-1] and dp[i-2], you never need more than two values at once. Replace the entire array with two variables: a = ways(n-2) and b = ways(n-1). At each step, compute new_b = a + b, then shift: a = b, b = new_b. After n-2 iterations starting from a=1, b=2, the answer is b. This is O(n) time and O(1) space.

Python O(1): def climbStairs(n): if n <= 2: return n; a, b = 1, 2; for _ in range(n-2): a, b = b, a+b; return b. Java O(1): if (n <= 2) return n; int a = 1, b = 2; for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; } return b. The Python simultaneous assignment a, b = b, a+b elegantly handles both the shift and the update in a single line.

The rolling-variable pattern eliminates O(n) memory entirely with no change to time complexity. For n=45 (the constraint) it makes no practical difference, but in production code where this function is called repeatedly or n can be large, O(1) space is strictly better. The interviewer wants to see you recognize the dependency window and explain why two variables suffice.

All three approaches — memoization, bottom-up DP, and O(1) rolling variables — solve LC 70. Python memoization: from functools import lru_cache; @lru_cache(maxsize=None); def climbStairs(n): return n if n <= 2 else climbStairs(n-1) + climbStairs(n-2). Python O(1) (4 lines): def climbStairs(n): a, b = 1, 1; for _ in range(n-1): a, b = b, a+b; return b. Note a=1,b=1 with n-1 iterations also works (Fibonacci offset). The clearest version initializes a=1, b=2 and loops n-2 times.

Java all three approaches: Memoization: private int[] memo; public int climbStairs(int n) { memo = new int[n+1]; return dp(n); } private int dp(int n) { if (n <= 2) return n; if (memo[n] != 0) return memo[n]; return memo[n] = dp(n-1) + dp(n-2); }. Bottom-up O(n) space: int[] dp = new int[n+1]; dp[1]=1; if(n>=2) dp[2]=2; for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2]; return dp[n]. O(1): int a=1,b=2; for(int i=3;i<=n;i++){int c=a+b;a=b;b=c;} return n<2?n:b.

For completeness: matrix exponentiation solves the Fibonacci recurrence in O(log n) time by computing [[1,1],[1,0]]^n. For LeetCode 70 with n<=45 this is academic, but it demonstrates that any linear recurrence with constant coefficients can be solved in O(log n) via fast matrix power — relevant for problems with very large n modulo a prime.

Min Cost Climbing Stairs (LeetCode 746) is the direct extension: add a cost array and minimize total cost instead of counting ways. The recurrence becomes dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The same O(1) rolling-variable optimization applies, but the base cases and the final return (min of last two values) differ slightly. Solving both back-to-back is the best way to internalize the linear DP template.

House Robber (LeetCode 198) uses the same two-state recurrence: dp[i] = max(nums[i] + dp[i-2], dp[i-1]). You cannot rob adjacent houses, so at each house you choose max of robbing it (current value plus dp two steps back) or skipping it (dp one step back). Decode Ways (LeetCode 91) adds a conditional: dp[i] depends on dp[i-1] (single digit decode) and dp[i-2] (two-digit decode, only if valid). Same window, conditional updates.

The Fibonacci family — Climbing Stairs, Min Cost Climbing Stairs, House Robber, Decode Ways, Jump Game II — all share the linear DP structure where dp[i] depends on a fixed small window of prior states. Mastering this family means mastering the core of 1D dynamic programming. When you see a 1D array problem asking for count or min/max with jumps of 1 or 2, the answer is always a linear DP with two-state rolling variables.