You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
Constraints:
1 <= n <= 45Problem Overview: You are given n steps. Each move allows climbing either 1 step or 2 steps. The task is to count how many distinct ways you can reach the top. The key observation: the number of ways to reach step n depends on the ways to reach n-1 and n-2.
Approach 1: Recursive Approach with Memoization (O(n) time, O(n) space)
The recurrence is straightforward: ways(n) = ways(n-1) + ways(n-2). From step n, the last move must have come from either n-1 (one step) or n-2 (two steps). A naive recursive solution recomputes the same subproblems repeatedly, leading to exponential time. Memoization fixes this by caching previously computed values in an array or hash map. Each state n is computed once, stored, and reused during later recursive calls. This turns the algorithm into linear time while still keeping the intuitive recursive structure. This pattern is common in memoization problems where overlapping subproblems appear.
Approach 2: Dynamic Programming (Bottom-Up) (O(n) time, O(n) space)
The bottom-up dynamic programming approach builds the solution iteratively. Create a DP array where dp[i] stores the number of ways to reach step i. Initialize base cases: dp[1] = 1 and dp[2] = 2. Then iterate from 3 to n and compute dp[i] = dp[i-1] + dp[i-2]. Each iteration represents combining the ways from the previous two steps. This is essentially the Fibonacci sequence, a classic example connecting math with dynamic programming. The iterative approach avoids recursion overhead and is usually the preferred implementation in production code.
Space can also be optimized because only the previous two states are needed. Instead of storing the full array, keep two variables representing dp[i-1] and dp[i-2]. Update them while iterating through the steps. This reduces space complexity to O(1) while keeping the same O(n) runtime.
Recommended for interviews: Start by explaining the recurrence relation since it shows you recognize the Fibonacci pattern. Then implement the bottom-up dynamic programming version. Interviewers expect the O(n) DP solution because it demonstrates understanding of overlapping subproblems and state transitions. Mentioning the space optimization to O(1) is a good signal that you understand how to refine DP implementations.
This approach uses recursion to explore the different ways to reach the top. To optimize, we use memoization to store results of subproblems to avoid redundant calculations. This ensures that each subproblem is solved only once, dramatically improving efficiency.
This C code provides a recursive solution enhanced with memoization. We define an array memo to store the results of previously solved subproblems. This helps in reducing redundant calculations, thus optimizing the recursive solution.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as each state is only computed once.
Space Complexity: O(n), due to the memoization array.
This approach builds from the base up using a table to store results at each step. Starting with known base cases, each subsequent result is built by combining previous results. This eliminates the recursive overhead, making it a very efficient algorithm.
This C code uses dynamic programming to solve the problem iteratively with a dp array. It starts with known results for 1 step and 2 steps and iteratively computes the number of ways for all steps up to n, reducing the time complexity compared to a naive recursive approach.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since each value is calculated sequentially in a loop.
Space Complexity: O(n), for storing the results in the dp array.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n), as each state is only computed once. |
| Dynamic Programming Approach | Time Complexity: O(n), since each value is calculated sequentially in a loop. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Recursion | O(2^n) | O(n) | Conceptual understanding of the recurrence relation |
| Recursion with Memoization | O(n) | O(n) | When using top-down DP or explaining recursion first |
| Dynamic Programming (Bottom-Up) | O(n) | O(n) | Standard interview solution with clear state transition |
| DP with Space Optimization | O(n) | O(1) | When memory usage matters or for a clean Fibonacci-style implementation |
Climbing Stairs - Dynamic Programming - Leetcode 70 - Python • NeetCode • 721,900 views views
Watch 9 more video solutions →Practice Climbing Stairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor