How many distinct ways can you climb n stairs taking 1 or 2 steps at a time?

Mid-level (3–5 years) Coding / DSA Medium

Reported in Multiverse Computing European engineering loops. Introductory dynamic programming problem isomorphic to Fibonacci.

Role: SDE
Location: Remote (EU)
Study track: Python

Interview scenario

Often asked in Multiverse Computing loops at European offices (London, Berlin, Amsterdam, Paris, Stockholm, Dublin, and remote EU). Prepare a clear spoken answer plus key trade-offs.

Spoiler-free prep mode

How to frame this at Multiverse Computing: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.

Define dp[i] = ways to reach step i. From step i you arrive from i-1 or i-2, so dp[i] = dp[i-1] + dp[i-2] with base dp[0]=1, dp[1]=1.

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Time O(n), space O(1) with rolling variables. Recognize Fibonacci structure—interviewers may ask for general k steps or memoized recursion top-down.

DP checklist: state definition, transition, base cases, iteration order, and optimization. Extension: climb with cost on steps (min cost path) uses different recurrence.

Discussion

Comments (0)

Share how this question came up in your loop, or add tips for others preparing.

Interview scenario

Try answering aloud first

Comments (0)