Climbing Stairs - Solution & Explanation
Problem Statement
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 <= 45
Approach Overview
Problem Overview: You are given n stairs. Each move allows either 1 step or 2 steps. The task is to compute the total number of distinct ways to reach the top. This is a classic recurrence problem where the number of ways to reach step i depends on the previous two steps.
Approach 1: Recursive with Memoization (Time: O(n), Space: O(n))
The recurrence relation is straightforward: to reach step n, you either come from step n-1 with a single step or from step n-2 with a double step. That leads to ways(n) = ways(n-1) + ways(n-2). A naive recursive solution recomputes the same subproblems repeatedly, resulting in exponential time. Memoization fixes this by storing results in a cache (array or hash map) and returning the stored value when the function encounters the same input again.
This turns the recursion into a top‑down dynamic programming solution. Each state is computed exactly once, giving O(n) time complexity and O(n) space for the memo table plus recursion stack. This approach is useful when you want to express the solution directly from the recurrence and let memoization handle repeated work.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n), Space: O(n))
The same recurrence can be solved iteratively. Create a DP array where dp[i] represents the number of ways to reach step i. Initialize the base cases: dp[1] = 1 and dp[2] = 2. Then iterate from 3 to n, computing dp[i] = dp[i-1] + dp[i-2]. Each iteration builds on previously computed states.
This bottom‑up dynamic programming approach avoids recursion and stack overhead. The recurrence is identical to the Fibonacci sequence, which is why this problem frequently appears in discussions of math patterns in DP problems. The algorithm performs a single pass through the array, giving O(n) time and O(n) space.
The space can also be optimized to O(1) by keeping only the last two values instead of the entire array. Since each state depends only on the previous two, two variables are sufficient to compute the sequence iteratively.
Recommended for interviews: Interviewers expect the dynamic programming interpretation. Starting with the recursive recurrence shows you understand the problem structure, especially if you mention memoization to eliminate repeated work. The strongest answer moves quickly to the bottom‑up DP or constant‑space Fibonacci-style iteration because it demonstrates recognition of the pattern and optimal implementation.
Approach 1: Recursive Approach with Memoization
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.
Complexity
Time Complexity: O(n), as each state is only computed once.
Space Complexity: O(n), due to the memoization array.
Approach 2: Dynamic Programming Approach
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.
Complexity
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 3: Recursion
We define f[i] to represent the number of ways to climb to the i-th step, then f[i] can be transferred from f[i - 1] and f[i - 2], that is:
$
f[i] = f[i - 1] + f[i - 2]
The initial conditions are f[0] = 1 and f[1] = 1, that is, the number of ways to climb to the 0th step is 1, and the number of ways to climb to the 1st step is also 1.
The answer is f[n].
Since f[i] is only related to f[i - 1] and f[i - 2], we can use two variables a and b to maintain the current number of ways, reducing the space complexity to O(1).
The time complexity is O(n), and the space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Approach 4: Matrix Quick Power to Accelerate Recursion
We set Fib(n) to represent a 1 times 2 matrix \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}, where F_n and F_{n - 1} are the n-th and (n - 1)-th Fibonacci numbers respectively.
We hope to derive Fib(n) based on Fib(n-1) = \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix}. That is to say, we need a matrix base, so that Fib(n - 1) times base = Fib(n), that is:
$
\begin{bmatrix}
F_{n - 1} & F_{n - 2}
\end{bmatrix} times base = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}
Since F_n = F_{n - 1} + F_{n - 2}, the first column of the matrix base is:
\begin{bmatrix}
1 \
1
\end{bmatrix}
The second column is:
\begin{bmatrix}
1 \
0
\end{bmatrix}
Therefore:
\begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} times \begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix} = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}
We define the initial matrix res = \begin{bmatrix} 1 & 1 \end{bmatrix}, then F_n is equal to the first element of the first row of the result matrix of res multiplied by base^{n - 1}. We can solve it using matrix quick power.
The time complexity is O(log n), and the space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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. |
| Recursion | — |
| Matrix Quick Power to Accelerate Recursion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | When expressing the recurrence naturally with recursion and caching subproblems |
| Dynamic Programming (Bottom-Up) | O(n) | O(n) or O(1) optimized | Preferred iterative solution for interviews and production code |
Video Solution
Climbing Stairs - Dynamic Programming - Leetcode 70 - Python • NeetCode • 853,397 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Climbing Stairs easy or hard?
Climbing Stairs Python/Java solution
How to solve Climbing Stairs in O(n)?
What is the best approach for Climbing Stairs?
Is Climbing Stairs asked at Google/Amazon/Meta?
What data structure is used in Climbing Stairs?
What is the time complexity of Climbing Stairs?
Ready to solve this problem?
Practice Climbing Stairs with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor