DSA Factory
Free lessonsDynamic programming · Stage 0 · Remember answers · Step 1

Climbing stairs

Plain recursion recomputes the same smaller cases over and over; a cache remembers them instead. About 11 minutes.

Think about your very last step

You're at the bottom of a staircase with n stairs, and each move climbs 1 or 2 stairs. How many different ways can you reach the top?

Listing every route by hand gets messy fast. So flip it around and ask about the last move instead. To stand on the top stair, you either stepped up one from the stair just below, or jumped two from the stair below that. There's no other way in.

So the ways to reach the top are the ways to reach the stair below, plus the ways to reach the one below that.

Ask about the last move: it splits one big count into two smaller ones.
The bottom is easy: there's 1 way to stand on the ground, and 1 way to reach stair 1.
In code
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

The same question, asked again and again

That code is correct, but give it 40 stairs and you'll be waiting a long time. Step through the calls below to see why.

Working out stair 4 asks about stair 3 and stair 2. But stair 3 asks about stair 2 again, completely from scratch. The smaller the stair, the more often it gets asked. For 40 stairs, the same handful of questions get answered hundreds of millions of times.

The slow part isn't the maths: it's answering the same question again and again.
The calls made by ways(4)
ways(4)ways(3)ways(2)ways(1)ways(0)ways(1)ways(2)ways(1)ways(0)

ways(4): the last move came from stair 3 or stair 2. So it asks ways(3) and ways(2).

Move 1 of 6

Write the answer down the first time

The fix is what you'd do on paper: keep a notebook. Before working anything out, check whether the answer is already written down. If it is, use it. If not, work it out, write it down, and then return it.

Now each stair is solved exactly once, so 40 stairs means about 40 small additions instead of hundreds of millions. This trick is called memoization (from "memo", a note to yourself), and it's the heart of dynamic programming.

Check the notebook first: a stair you've already solved costs nothing.
Memoization: the same recursion, plus a notebook of answers.
In code
memo = {}
def ways(n):
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways(n-1) + ways(n-2)
    return memo[n]
Quick check

Without a cache, how many times does plain recursion compute ways(2) while working out ways(6)?

  1. AMore than once
  2. BExactly once
Show the answer

More than once. ways(2) is needed by ways(3) and ways(4), which are both called separately, so ways(2) gets recomputed.

Your problem

Climbing stairs

A staircase has n stairs. From any stair, you can move up by 1 or by 2. Return the number of distinct ways to go from the ground (stair 0) to stair n.

Example
n = 4 → 5

0 ≤ n ≤ 48

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding