How do you solve the climbing stairs problem?

Q: How do you solve the climbing stairs problem?

**Target Audience:** Beginners preparing for coding interviews; this is usually the first dynamic programming problem people meet. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A child runs up the stairs to bed. Sometimes she takes one step, sometimes she jumps two. Her older brother, bored, asks: "There are 5 stairs. How many different ways can you go up?" She starts listing — 1-1-1-1-1, 2-1-1-1, 1-2-1-1, … — loses track, and gives up. Here is the trick that makes it easy. Stand on the top stair and look back. **How did you get here?** Your last move was e

The problem

Question presented to candidate: "You are climbing a staircase with n steps. Each move you climb either 1 or 2 steps. In how many distinct ways can you reach the top? Please write it in Python, start with whatever is simplest, then make it efficient."

What a strong answer should cover:

The recurrence from the last move, ways(n) = ways(n - 1) + ways(n - 2), and why the two cases do not overlap.
Correct base cases (ways(0) = ways(1) = 1) and the link to Fibonacci.
Why plain recursion is exponential, and the progression memo → table → two variables (O(n) time, O(1) space).
Generalising to any set of step sizes, or to min cost climbing stairs.
Python specifics: tuple assignment for the two-variable shift, int never overflowing (exact climb(92)), and the 1000-frame recursion limit that makes the memo version fail for large n.

Clarifying questions expected:

"Are the moves exactly 1 or 2 steps, and does order matter?"
"How large can n be — do I need 64-bit numbers or a modulo?"

Code / implementation expected: Yes — a short Python function, ideally the O(1)-space loop.

dp
climbing-stairs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; this is usually the first dynamic programming problem people meet. Difficulty: Easy Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A child runs up the stairs to bed. Sometimes she takes one step, sometimes she jumps two. Her older brother, bored, asks: "There are 5 stairs. How many different ways can you go up?" She starts listing — 1-1-1-1-1, 2-1-1-1, 1-2-1-1, … — loses track, and gives up.

Here is the trick that

The solution is hidden so you can try first

8 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonFour solutions that agree: naive recursion (with call counts), memo, table and two variables

Practice

PythonVariants with the same recipe: any set of step sizes, and min cost climbing stairs

Practice

PythonHow big the answer gets: exact values, 32-bit wrap-around and the 2^53 limit