Climbing Stairs: Dynamic Programming in Python and TypeScript

The Climbing Stairs Problem

A staircase has n steps. Each move climbs either one step or two. Return the number of distinct ways to reach the top. Two ways are different if the sequence of moves is different.

Example 1

Input: n = 3
Output: 3
Why: the three ways are 1+1+1, 1+2 and 2+1.

Example 2

Input: n = 5
Output: 8
Why: list a few small cases (1, 2, 3, 5, 8) and a pattern appears: each answer is the sum of the two before it.

Assumptions to confirm

• Is n at least 1? (What should n = 0 return? Many definitions say 1, the empty climb, but ask.)
• How large can n get? (The answer grows exponentially, so very large n can overflow 32-bit integers.)
• Are the allowed step sizes always 1 and 2?

Start With Plain Recursion

The last move onto step n is either a single step from n - 1 or a double step from n - 2. So the ways to reach n are ways(n - 1) + ways(n - 2), with ways(1) = 1 and ways(2) = 2. A recursive function that follows this definition is correct, but each call makes two more calls, so it takes exponential time: roughly O(2ⁿ).

Say why it is slow: ways(n - 2) is computed again inside ways(n - 1), and the same smaller values are recalculated over and over. Storing each answer the first time you compute it (memoisation) brings it to O(n) time and O(n) space. Building the values from the bottom up, keeping only the last two, brings the space down to O(1).

The Optimal Approach: Build Up From the Bottom

Climbing Stairs Solution in Python and TypeScript

Both versions keep only two numbers, which is the bottom-up form of the recurrence ways(n) = ways(n - 1) + ways(n - 2).

Python

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    one_back, two_back = 2, 1  # ways to reach step 2 and step 1
    for _ in range(3, n + 1):
        one_back, two_back = one_back + two_back, one_back
    return one_back

TypeScript

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let oneBack = 2; // ways to reach step 2
  let twoBack = 1; // ways to reach step 1
  for (let step = 3; step <= n; step++) {
    const ways = oneBack + twoBack;
    twoBack = oneBack;
    oneBack = ways;
  }
  return oneBack;
}

The sequence 1, 2, 3, 5, 8, 13 is the Fibonacci sequence shifted by one. You do not need to know that to solve the problem, but noticing it shows you understand the recurrence.

Time and Space Complexity

How to Talk Through Climbing Stairs in an Interview

A strong spoken answer follows the same five beats every time:

1. Clarify: "Only one or two steps at a time? What should n = 0 return? How large can n be?"
2. Brute force: "The last move comes from n - 1 or n - 2, so ways(n) = ways(n - 1) + ways(n - 2). Plain recursion is exponential because it repeats work."
3. Optimise: "Each value depends only on the two before it, so I can build up from the bottom and keep just two numbers."
4. Code: name the variables after what they mean, such as ways to reach one step back and two steps back.
5. Test: check n = 1, 2, 3 and 5 against values you listed by hand. State O(n) time and O(1) space.

This problem is a common first test of dynamic programming. Going from recursion to memoisation to two variables, and explaining each step, is exactly the reasoning interviewers want to see.

Edge Cases and Common Follow-Ups

Practise Climbing Stairs in a Mock Coding Round

Climbing Stairs is short enough that the code is rarely the problem. What interviewers listen for is whether you can derive the recurrence yourself and explain why plain recursion is slow. That reasoning is much easier to show if you have practised saying it out loud.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions