Climbing Stairs LeetCode Solution: Complete Walkthrough

Climbing stairs leetcode problem number 70 is the first dynamic programming question most people encounter — and for good reason. It is simple enough to build genuine intuition about what DP means, yet deep enough to teach a recurrence pattern you will use dozens of times in harder problems.

If you have ever felt that dynamic programming is mysterious or intimidating, this is the problem that should change your mind. There are no tricky edge cases, no complicated state transitions, and no multidimensional arrays. Just one clean recurrence relation that reveals the core idea behind every DP problem: break a big question into smaller overlapping subproblems.

In this walkthrough you will see three progressively better approaches — pure recursion, memoization, and tabulation — followed by a space optimization that brings memory usage down to O(1). By the end you will understand the climbing stairs dp pattern well enough to recognize it in House Robber, Decode Ways, and Tribonacci.

The problem statement is straightforward. You are climbing a staircase with n steps. Each time you can climb either one step or two steps. How many distinct ways can you reach the top?

Take a small example. With three steps you can climb 1-1-1, 1-2, or 2-1 — three distinct ways. With four steps you get five ways. Notice something familiar? The sequence 1, 2, 3, 5, 8 follows the Fibonacci pattern exactly.

The reason is elegant. To reach step n you must have come from either step n-1 (by taking one step) or step n-2 (by taking two steps). So the number of ways to reach step n equals the sum of the ways to reach step n-1 and step n-2. That gives us dp(n) = dp(n-1) + dp(n-2) — the Fibonacci recurrence.

Once you see that climbing stairs is secretly Fibonacci, the entire solution strategy becomes clear. The only question is how efficiently you compute it.

The most intuitive approach is direct recursion. Define a function climbStairs(n) that returns climbStairs(n-1) + climbStairs(n-2) with base cases returning 1 for n equals 1 and 2 for n equals 2. This reads almost like the mathematical definition itself.

The problem is performance. Each call branches into two more calls, creating a binary tree of recursive invocations. The time complexity is O(2^n), which is catastrophic. For n equals 45, you would make over 3.5 billion recursive calls.

The climbing stairs recursive approach fails on LeetCode with a Time Limit Exceeded verdict. But it is not useless — it exposes exactly why dynamic programming exists. The recursion tree contains massive redundancy. climbStairs(3) gets called millions of times with the same argument, always returning the same result.

This redundancy is the hallmark of overlapping subproblems, one of the two properties that make a problem suitable for DP. The other property, optimal substructure, is also present since the answer for n depends directly on smaller subproblems.

The fix for the exponential recursion is simple: cache every result. Before computing climbStairs(n), check whether you have already stored the answer. If so, return it immediately. If not, compute it, store it, and then return it.

This technique is called memoization, and it transforms the climbing stairs dp solution from O(2^n) to O(n) time. Each value from 1 to n is computed exactly once and looked up in constant time for every subsequent call. The space complexity is O(n) for the memo table plus O(n) for the recursion stack.

In Python you can use a dictionary or the built-in functools.lru_cache decorator. In Java or C++ you typically use an array of size n+1 initialized to negative one. The implementation details vary by language but the idea is identical — store results to avoid redundant computation.

Top-down memoization preserves the recursive structure of the problem, which some people find more natural to reason about. You start from the big problem and let recursion discover which subproblems are needed. The cache ensures no subproblem is solved more than once.

The bottom-up approach flips the direction. Instead of starting from n and recursing down, you start from the base cases and build upward. Create an array dp where dp[1] equals 1 and dp[2] equals 2, then iterate from 3 to n, setting dp[i] = dp[i-1] + dp[i-2].

Tabulation has the same O(n) time complexity as memoization but avoids recursion stack overhead entirely. This makes it slightly faster in practice and eliminates any risk of stack overflow for large inputs.

The real win comes from noticing that each dp[i] only depends on the previous two values. You do not need the full array — just two variables. Replace the array with prev1 and prev2, update them in each iteration, and you have an O(1) space solution.

This space-optimized version is the leetcode 70 solution that experienced interviewers expect to see. It runs in O(n) time and O(1) space, which is optimal. The code is just a few lines: initialize two variables, loop from 3 to n, and swap-update them like computing Fibonacci with two variables instead of an array.

The climbing stairs explained solution must handle a few edge cases cleanly. When n equals 1 the answer is 1. When n equals 2 the answer is 2. When n equals 0 the answer is technically 1 because there is exactly one way to stay at the ground — doing nothing. Most implementations handle n equals 0 as a special return.

A common variant is Min Cost Climbing Stairs, LeetCode problem 746. Instead of counting distinct paths you minimize the total cost, where each step has an associated price. The recurrence changes from summing paths to taking the minimum of two options, but the Fibonacci-style structure is identical.

House Robber, LeetCode problem 198, uses the exact same recurrence pattern. You choose whether to rob each house (analogous to taking one or two steps), and the state transition is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Once you master climbing stairs, House Robber feels like the same problem with a different coat of paint.

The Fibonacci recurrence pattern from climbing stairs leetcode is not just one trick — it is a template that appears in a surprising number of problems. Whenever you see a question that asks how many ways to reach a goal where you can choose from a small set of options at each step, you should immediately think of this pattern.

The progression from recursion to memoization to tabulation to space optimization is a workflow you will repeat for every DP problem you encounter. Start with the brute-force recursive definition to confirm correctness. Add memoization to eliminate redundancy. Convert to bottom-up iteration if you want cleaner performance. Then look for variables you can drop to reduce space.

If you are preparing for coding interviews, spend extra time on this problem. Practice writing all three approaches from memory. Once climbing stairs feels effortless, move to House Robber, then Decode Ways, then Tribonacci. Each one adds a small twist but uses the same fundamental recurrence. Build your DP intuition with YeetCode flashcards to make these patterns automatic.

The biggest takeaway from the fibonacci dynamic programming approach is that DP is not about memorizing solutions. It is about recognizing that a problem has overlapping subproblems and optimal substructure, writing the recurrence relation, and choosing the most efficient way to compute it. Climbing Stairs teaches all of this in the simplest possible setting.