Skip to main content

70. Climbing Stairs

easyAsked at Cohere

Count distinct ways to reach the nth stair taking 1 or 2 steps at a time. Cohere uses this to gauge whether candidates recognise overlapping subproblems — a mental model critical for understanding dynamic-programming approaches in sequence modelling.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q3)— Cohere candidates report this as a frequent introductory DP problem in early interview rounds.
  • Blind (2025-08)— Listed in a Cohere prep guide as an easy DP warm-up before harder sequence problems.

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) or (2).

Example 2

Input
n = 3
Output
3

Explanation: Three ways: (1,1,1), (1,2), or (2,1).

Approaches

1. Naive recursion (exponential)

Recursively compute ways(n) = ways(n-1) + ways(n-2). No memoization — recomputes the same subproblems exponentially.

Time
O(2^n)
Space
O(n) call stack
function climbStairs(n) {
  if (n <= 1) return 1;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Tradeoff: Illustrates the recurrence but is far too slow. Mention it only to set up the DP optimisation.

2. Bottom-up DP (space-optimised)

Notice that ways(n) depends only on the previous two values — equivalent to Fibonacci. Use two variables instead of an array.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 1) return 1;
  let prev2 = 1, prev1 = 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 — the canonical answer. Recognising the Fibonacci connection and space-optimising the DP table is what interviewers want to see.

Cohere-specific tips

Cohere values candidates who articulate the recurrence relation before coding: 'To reach step n I must have come from step n-1 or n-2, so the number of ways is the sum of those two sub-answers.' Tie this to how token-level decoding in language models uses previously-computed states — beam search and dynamic programming share the overlapping-subproblem insight.

Common mistakes

  • Off-by-one on base cases — ways(0) = 1 (one way: do nothing) and ways(1) = 1 are both needed.
  • Initialising prev1 and prev2 incorrectly — trace through n=2 before submitting.
  • Using memoization with a full array when two variables suffice.
  • Not recognising this as Fibonacci — an interviewer at Cohere may ask you to name the pattern.

Follow-up questions

An interviewer at Cohere may pivot to one of these next:

  • Climbing Stairs with k step sizes — dp[i] = sum of dp[i-1] to dp[i-k].
  • Minimum cost climbing stairs (LC 746) — attach costs to each step.
  • How does this relate to beam search in sequence decoding?

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 ways(0) = 1?

There is exactly one way to be at the bottom: do nothing. This base case is required for the recurrence to produce correct values for n=1 and n=2.

What is the largest n this runs on without overflow?

n=45 produces 1,836,311,903 which fits in a 32-bit signed integer. For larger n you would need BigInt.

Can you compute this in O(log n)?

Yes, using matrix exponentiation of the Fibonacci recurrence — worth mentioning if the interviewer asks about very large n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →