Introduction

The Climbing Stairs problem is one of the most popular Dynamic Programming interview questions.

You are given:

n stairs

At every step, you can climb:

1 stair or 2 stairs

Goal:

Find total number of distinct ways to reach the top.

Example:

n = 4Output = 5

Ways:

1+1+1+11+1+2
1+2+1
2+1+1
2+2

This problem is a direct application of:

Fibonacci DP

Constraints

1 <= n <= 45

Observation

To reach stair:

n

You can come from:

n - 1 or n - 2

Therefore:

dp[n] = dp[n-1] + dp[n-2]

This is exactly the Fibonacci recurrence.

Approach 1 : Memoization

Explanation

Use recursion and store previously computed answers.

Steps:

  1. Solve recursively.
  2. Save result.
  3. Reuse stored values.
  4. Avoid repeated calculations.

Dry Run

n = 4ways(4) = ways(3) + ways(2) = 3 + 2 = 5

Memo Table:

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5

Approach 2 : Tabulation

Explanation

Build answers from smaller values.

Base Cases:

dp[1] = 1
dp[2] = 2

Transition:

dp[i] =  dp[i-1] + dp[i-2]

Approach 3 : Space Optimized DP

Explanation

Only previous two answers are required.

Instead of storing an entire DP array:

prev2prev1

Use two variables.

This reduces:

Space Complexity to O(1)

Practice

Complexity Analysis

Memoization

Time Complexity: O(n)

Space Complexity: O(n)

Tabulation

Time Complexity: O(n)
Space Complexity: O(n)

Space Optimized DP

Time Complexity: O(n)
Space Complexity: O(1)

Why This Problem is Important

This problem teaches:

  • Dynamic Programming
  • Recurrence Relations
  • Memoization
  • Tabulation
  • Space Optimization

Real-World Applications

Used in:

  • Path Counting Problems
  • Grid Traversal
  • Resource Planning
  • Optimization Algorithms
  • State Transition Problems

Common Beginner Mistakes

  • Wrong base cases
  • Using recursion only
  • Forgetting DP relation
  • Incorrect loop range
  • Missing space optimization

Interview Tip

Interviewers often expect:

Recursion→ Memoization
→ Tabulation
→ Space Optimization

Always explain:

  • how recurrence is formed
  • why Fibonacci appears
  • how DP avoids recomputation

Related Questions

  • Fibonacci
  • Min Cost Climbing Stairs
  • House Robber
  • Coin Change
  • Decode Ways

Final Takeaway

Climbing Stairs is one of the best beginner Dynamic Programming problems.

It teaches:

  • DP thinking
  • State transitions
  • Recurrence relations
  • Space optimization

Mastering this problem makes it much easier to solve advanced Dynamic Programming questions.