Log inSign up
easyLeetCodeNot Started

Climbing Stairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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

### Example 3 - Input: n = 4 - Output: 5 - Explanation: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2].

Constraints:

  • 1 <= n <= 45

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify overlapping subproblems and optimal substructure in step-counting.
  • Formulate the base cases and recurrence relation.
  • Optimize from O(n) space to O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting distinct ways to reach a target.
  • Allowed steps are fixed small increments (e.g., 1 or 2).
  • Classic additive subproblem structure.

Algorithmic Decision Tree:

  • Step count = sum of ways from all valid previous step landings.
  • If steps are {1, 2} -> Fibonacci recurrence.

Connected Patterns:

Min Cost Climbing StairsHouse RobberDecode Ways

1. Naive Recursion

Intuition

Branch at each step by either taking 1 step or 2 steps until n is reached.

Algorithm

  1. Define climb(n).
  2. If n <= 2, return n.
  3. Return climb(n - 1) + climb(n - 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int climbStairsRec(int n) {
6 if (n <= 2) return n;
7 return climbStairsRec(n - 1) + climbStairsRec(n - 2);
8}
9
10int main() {
11 int n = 4;
12 cout << "Ways to climb " << n << " stairs (Recursive): " << climbStairsRec(n) << endl;
13 return 0;
14}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) recursion call stack

2. Dynamic Programming Tabulation

Intuition

Maintain array dp of size n + 1 where dp[i] = dp[i - 1] + dp[i - 2].

Algorithm

  1. If n <= 2, return n.
  2. Create array dp of size n + 1.
  3. dp[1] = 1, dp[2] = 2.
  4. For i = 3 to n:
  5. dp[i] = dp[i - 1] + dp[i - 2].
  6. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int climbStairsDP(int n) {
7 if (n <= 2) return n;
8 vector<int> dp(n + 1);
9 dp[1] = 1;
10 dp[2] = 2;
11 for (int i = 3; i <= n; i++) {
12 dp[i] = dp[i - 1] + dp[i - 2];
13 }
14 return dp[n];
15}
16
17int main() {
18 int n = 4;
19 cout << "Ways to climb " << n << " stairs (DP Table): " << climbStairsDP(n) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for dp array

3. O(1) Space Rolling Variables

Intuition

Keep only the previous two steps in scalars prev2 and prev1.

Algorithm

  1. If n <= 2, return n.
  2. prev2 = 1, prev1 = 2.
  3. For i = 3 to n:
  4. curr = prev1 + prev2
  5. prev2 = prev1
  6. prev1 = curr
  7. Return prev1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int climbStairsOptimal(int n) {
6 if (n <= 2) return n;
7 int prev2 = 1;
8 int prev1 = 2;
9
10 for (int i = 3; i <= n; i++) {
11 int curr = prev1 + prev2;
12 prev2 = prev1;
13 prev1 = curr;
14 }
15 return prev1;
16}
17
18int main() {
19 int n = 4;
20 cout << "Ways to climb " << n << " stairs (Optimal O(1) Space): " << climbStairsOptimal(n) << endl;
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive RecursionO(2^n)O(n)climb(n-1) + climb(n-2) recursion tree.Redundant subtrees
2.DP TabulationO(n)O(n)Store ways up to step n in array.Array memory
3.Rolling VariablesOptimalO(n)O(1)Maintain prev2 and prev1 scalars.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Setting dp[0] = 0 instead of considering base case n = 1 -> 1, n = 2 -> 2.

Pitfall 2:

Using recursion without memoization.

Crucial Edge Cases to Validate:

  • n = 1: Exactly 1 way.
  • n = 2: Exactly 2 ways.
  • n = 45: Largest constrained input, comfortably fits within 32-bit signed integer.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State immediately that this problem is isomorphic to Fibonacci.
  2. Mention that if n was up to 109, matrix exponentiation or Binet's formula could compute the answer in O(log n) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the number of ways to climb n stairs correspond to Fibonacci numbers?

Back to DSA Sheet