• 1 ≤ n ≤ 45
• Every move is exactly 1 step or exactly 2 steps
• The answer fits in a signed 32-bit integer

You start on the ground. We call it step 0. The top is step n. Each move goes up by 1 step or by 2 steps. A "way" is the full ordered list of moves you made.

Take n = 3. The ways are 1+1+1, 1+2, and 2+1. That is three ways. Look at 1+2 and 2+1. They use the same move sizes, but in a different order, and we count them as two separate ways. This one detail matters. It means we count the order of moves, not just which move sizes we used.

We are not asked for the cheapest way or the shortest way. We are asked how many. So our solution will add things up, not take a minimum.

Your first instinct is to start at the bottom and walk up. From step 0 you can go to 1 or 2. From 1 you can go to 2 or 3. And so on. This works, but it gets messy fast. Every step splits into two more. Soon you are tracking a huge number of half-finished climbs at once.

There is a cleaner way to think. Stand at the top and look backward.

Say you just arrived on step n. Your last move was either a 1-step or a 2-step. There is no third option. So there are only two cases:

Every climb ends in exactly one of these two cases, and no climb is in both. So the number of climbs that end on step n is:

(climbs that end on step n-1) + (climbs that end on step n-2).

Read that once more. We just described the answer for a big staircase using only the answers for two smaller staircases. We never had to picture a full list of moves. That is the whole trick.

A recursive function solves a big problem by calling itself on smaller versions of the same problem. This sounds circular, but it is not, as long as two things hold. First, every call it makes is on a strictly smaller problem. Second, there are tiny problems it can answer at once, without calling itself. Those tiny cases are the base cases. Without them the function shrinks forever and never returns.

Here is the habit that unlocks almost every DP problem: write the answer as a function of the things that change. So look at the staircase and ask: as I move around, what actually changes? Only one thing — the step I am standing on. Everything else is fixed. So the function needs just one input, the step number:

Let f(i) = the number of ways to reach step i from the ground.

Those changing inputs are called the state. Here the state is only i. Nothing else about your past matters: two climbers on step 5 have the same number of ways left, no matter how they got there. So the index alone is the state. Find the values that change, and you have found the function to write.

Our backward argument now fills in what f(i) does. This is the recurrence — the formula that builds a state from smaller states:

f(i) = f(i-1) + f(i-2)

Now the base cases. f(0) is the number of ways to be on the ground. That is 1: do nothing. "One way to do nothing" can feel odd, so here is a quick check. f(2) should be 2 (1+1 and 2). The recurrence says f(2) = f(1) + f(0). And f(1) is clearly 1 (one 1-step hop). So f(0) has to be 1 for the math to work out. That gives f(0) = 1 and f(1) = 1.

def f(i):
    if i == 0: return 1     # already at the ground: one way (do nothing)
    if i == 1: return 1     # one hop of size 1
    return f(i - 1) + f(i - 2)

This is fully correct. It is also far too slow, and the reason is worth seeing for yourself.

Trace what f(5) really does. It calls f(4) and f(3). But f(4) also calls f(3) and f(2). So f(3) runs twice, from two different places, and neither call knows about the other. One level deeper, f(2) runs three times. Deeper still, the repeats blow up.

Every call splits into two calls. The call tree is about n levels deep. So the number of calls is roughly 2ⁿ. For n = 45 that is about 35 trillion calls, just to find a number your calculator returns at once. And here is the worst part: every repeated call returns the same answer as before. f(3) gives the same value the first time and the fifth time you ask. We pay full price again and again for a result we already had.

Memoisation means keeping a notebook. Before you do any work for state i, check the notebook. If the answer is already there, return it right away. If not, compute it the normal way, and write it in the notebook before you return. The next caller gets it for free.

def climb(n):
    memo = {}                       # the notebook

    def f(i):
        if i == 0: return 1
        if i == 1: return 1
        if i in memo: return memo[i]     # already solved: hand it back
        memo[i] = f(i - 1) + f(i - 2)    # solve once, then record it
        return memo[i]

    return f(n)

Now count again. There are only n+1 different states, f(0) through f(n). Each one does its real work exactly once. After that, every request for it is a quick notebook lookup. So the total work grows with n. We went from 2ⁿ to about n by adding three lines. The memory cost is an array of size n+1 for the notebook, plus the depth of the nested calls, which is also about n.

This style is called top-down. You ask the big question first, and it drills down to the small ones only when it needs them.

Look at the recurrence again. f(i) needs f(i-1) and f(i-2). It only ever reaches down, toward smaller indices. So if we compute the answers in increasing order — f(0), then f(1), then f(2) — then by the time we reach any i, both values it needs are already there, finished. No recursion needed. Just a loop and an array.

This switch is mechanical. It is the same few moves every time:

def climb(n):
    if n == 1: return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Same O(N) time, but now there is no call stack at all. That makes it safe from stack overflow on large inputs, which is a real advantage in languages with a shallow recursion limit.

Look at what one loop step touches: dp[i], dp[i-1], dp[i-2]. Never dp[i-7]. Once an index is more than two steps behind, nothing will read it again. It is dead weight. So why keep the whole array? Two variables are enough.

def climb(n):
    if n == 1: return 1
    two_back, one_back = 1, 1        # dp[0], dp[1]
    for i in range(2, n + 1):
        current = one_back + two_back
        two_back, one_back = one_back, current   # slide the window up by one
    return one_back

O(N) time, O(1) space. The rule is general: your table only needs to be as wide as the furthest back your recurrence reaches. Reach back two, keep two.

Sanity-check the small one by hand: for n = 3 the loop gives 3, and we listed exactly three sequences at the top of the page. The machine agrees with the paper.

Many counting and best-value problems come down to the same four questions, asked in the same order. When you meet a new one, write these down before you write any code:

Answer those four, and the rest follows a fixed recipe: write the recursion straight from the recurrence, add memoisation to kill repeats, switch to a table to kill the call stack, then trim the table to the width your recurrence reaches back.

One last thing. This recurrence is the Fibonacci sequence. That is not a fact to memorise. It simply fell out of having two ways to arrive and adding them. Learn to spot the shape, not the name.