Skip to main content

70. Climbing Stairs

easyAsked at Juniper Networks

Count distinct ways to climb n stairs taking 1 or 2 steps at a time. Juniper uses this as a gentle DP introduction — the recurrence mirrors hop-count path enumeration in network topology analysis where you want to count distinct routes between two routers with a maximum hop constraint.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q3)— Reported in Juniper university-hire onsite reports as an introductory dynamic-programming question.
  • Blind (2025-08)— Listed in Juniper interview prep threads as a Fibonacci-pattern DP warm-up.

Problem

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?

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 2
Output
2

Explanation: Two ways: [1,1] and [2].

Example 2

Input
n = 3
Output
3

Explanation: Three ways: [1,1,1], [1,2], [2,1].

Approaches

1. Memoized recursion (top-down DP)

Recurse with a memo table to avoid recomputing subproblems.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function dp(i) {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i);
    const res = dp(i - 1) + dp(i - 2);
    memo.set(i, res);
    return res;
  }
  return dp(n);
}

Tradeoff: O(n) time and space. Good for explaining the DP recurrence clearly.

2. Bottom-up DP with two variables — O(1) space

The answer at step i is dp[i-1] + dp[i-2]. Since we only ever look back two steps, we only need two variables.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n === 1) return 1;
  let prev2 = 1; // ways to reach step 0 (or 1)
  let prev1 = 1; // ways to reach step 1
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space. Identical recurrence to Fibonacci. Preferred by Juniper for its low memory footprint.

Juniper Networks-specific tips

Recognize and name the Fibonacci pattern before coding — Juniper interviewers reward candidates who identify the recurrence structure before jumping into code. Tie it to networking: counting distinct paths between two nodes with a hop limit follows the same combinatorial recurrence. Offer the O(1)-space bottom-up solution as your final answer.

Common mistakes

  • Initializing the base cases wrong — dp[1] = 1 and dp[2] = 2, or equivalently dp[0] = 1 and dp[1] = 1 (counting ways to reach each step).
  • Using a full O(n) array when only two previous values are needed.
  • Trying to use closed-form Fibonacci with floating-point — introduces rounding error for large n.
  • Forgetting the n=1 edge case in the two-variable approach.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • What if you could climb 1, 2, or 3 steps? Generalize the recurrence.
  • Minimum Cost Climbing Stairs (LC 746) — add a cost to each step.
  • How many distinct paths exist between two routers with at most k hops in a graph?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this the Fibonacci sequence?

To reach step n you must arrive from step n-1 (one step) or step n-2 (two steps). The number of ways is the sum — exactly the Fibonacci recurrence with base cases f(1)=1, f(2)=2.

Can n be 0?

The constraint says n >= 1. If asked, 0 stairs means 1 way (do nothing), which is consistent with f(0) = 1 in the Fibonacci interpretation.

What is the maximum value for n=45?

f(45) = 1,836,311,903 which fits in a 32-bit integer. No big-integer handling needed within the given constraints.

Practice these live with InterviewChamp.AI

Drill Climbing Stairs and other Juniper Networks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →