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 <= 45The key idea behind #70 Climbing Stairs is recognizing that the number of ways to reach step n depends on how you reached the previous steps. From any step, you can either climb 1 or 2 stairs. This leads to the recurrence relation: the ways to reach step n equals the sum of ways to reach n-1 and n-2. This pattern closely resembles the Fibonacci sequence.
A straightforward recursive solution exists but results in repeated computations, making it inefficient. To optimize this, you can use memoization (top-down dynamic programming) to store previously computed results and avoid recomputation. Another approach is bottom-up dynamic programming, where you iteratively build solutions from smaller steps up to n.
For further optimization, since only the last two states are required, the DP array can be reduced to two variables, achieving O(1) space complexity while maintaining O(n) time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Recursion | O(2^n) | O(n) |
| Dynamic Programming (Memoization / Tabulation) | O(n) | O(n) |
| Space Optimized DP | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
To reach nth step, what could have been your previous steps? (Think about the step sizes)
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.
Time Complexity: O(n), as each state is only computed once.
Space Complexity: O(n), due to the memoization array.
1#include <stdio.h>
2#define MAX 46
3
4int memo[MAX] = {0};
5
6int climbStairs(int n) {
7 if (n == 1) return 1;
8 if (n == 2) return 2;
9 if (memo[n] != 0) return memo[n];
10 memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
11 return memo[n];
12}
13
14int main() {
15 int n = 3;
16 printf("%d", climbStairs(n));
17 return 0;
18}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.
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.
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.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Climbing Stairs is a very common beginner-level interview problem at companies like Google, Amazon, and Meta. It tests a candidate’s understanding of dynamic programming and recognizing Fibonacci-like patterns.
Dynamic programming structures such as arrays or simple variables are typically used. In memoization, a hash map or array stores previously computed results to avoid redundant recursion.
The optimal approach uses dynamic programming based on the Fibonacci pattern. Each step depends on the number of ways to reach the previous two steps. A space-optimized DP solution achieves O(n) time and O(1) space complexity.
The number of ways to reach step n equals the sum of ways to reach steps n-1 and n-2. This recurrence relation is identical to the Fibonacci sequence, making the problem a classic DP example.
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.