Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Climbing Stairs

Problem (restated)

You can climb 1 or 2 steps. How many distinct ways to reach the top of n steps?

Intuition

ways(n) = ways(n-1) + ways(n-2). Fibonacci with rolling variables.

Approaches

1D DP

Tested only

Time O(n)Space O(1)

Idea. dp[i] = dp[i-1] + dp[i-2]; keep only two previous values.

Walkthrough. n=3 → 3 ways: 1+1+1, 1+2, 2+1.

Trade-offs. Closed form possible but DP is interview-clear.

Solution

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

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

Template connection

One-dimensional DP linear recurrence.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?