Climbing Stairs

Climbing Stairs

What is this problem about?

You are climbing a staircase that has $n$ steps. Each time you can either take 1 or 2 steps. In how many distinct ways can you climb to the top? This is one of the most famous and foundational problems in computer science.

Why is this asked in interviews?

Asked by nearly every major tech company (Apple, Amazon, Google, etc.), "Climbing Stairs" is the ultimate test of your understanding of Recursion and Dynamic Programming. It demonstrates how a problem that looks complex can be reduced to a simple mathematical sequence (Fibonacci). It evaluations your ability to identify overlapping subproblems and optimize your code from $O(2^n)$ to $O(n)$.

Algorithmic pattern used

The pattern is Dynamic Programming or Memoization. To reach step $n$, you must have come from either step $n-1$ (with a 1-step move) or step $n-2$ (with a 2-step move). Therefore, $Ways(n) = Ways(n-1) + Ways(n-2)$. This is exactly the Fibonacci sequence. You can solve it iteratively using two variables to achieve $O(1)$ space.

Example explanation

$n = 3$

• To reach step 3, you could:
  1. Come from step 2 (Ways to reach 2: [1,1], [2]).
  2. Come from step 1 (Ways to reach 1: [1]).
• Total ways = (Ways to reach 2) + (Ways to reach 1) = 2 + 1 = 3. Paths: [1,1,1], [1,2], [2,1].

Common mistakes candidates make

The most common mistake is using naive recursion without memoization, which leads to exponential time complexity and a "Time Limit Exceeded" error. Another mistake is not recognizing the base cases correctly ($n=1$ is 1 way, $n=2$ is 2 ways). Some might also struggle with integer overflow if $n$ is very large (though standard 32-bit or 64-bit integers usually suffice for interview constraints).

Interview preparation tip

This is the "Hello World" of Dynamic Programming. Master the transition from recursion -> memoization -> iterative DP -> space-optimized DP. If you can explain this progression, you've demonstrated a core competency in algorithm design.