Climbing Stairs

📌 Definition:

📖 Detailed Explanation:

The number of ways to reach step n equals ways(n-1) + ways(n-2) — the Fibonacci recurrence, because your last move was either a 1-step from n-1 or a 2-step from n-2. Solve it bottom-up with two rolling variables in O(n) time, O(1) space; naive recursion is exponential.

💻 Solutions:

• Java
• JavaScript
• Python

public static int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

🔑 Key Points:

• ways(n) = ways(n-1) + ways(n-2) (Fibonacci)
• Bottom-up with two rolling variables
• O(n) time, O(1) space
• Naive recursion is O(2^n)

🌍 Real-World Example: