070. Climbing Stairs

At a Glance

• Topic: Dynamic Programming
• Pattern: DP
• Difficulty: Easy
• LeetCode: 070

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

Constraints:

1 <= n <= 45

Approach & Solution Steps

Use a bottom-up dynamic programming approach. The number of ways to reach step i is the sum of ways to reach step i-1 and i-2. Keep track of the last two values to optimize space.

Optimal JS Solution

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

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.