Climbing Stairs

The reliable way to solve Climbing Stairs is to stop guessing “Fibonacci” and ask one structural question: what could the final move have been?

The short answer

You need to count the distinct sequences of moves that reach step n. Each move advances exactly 1 or 2 steps, and order matters.

For example:

• n = 2: 1 + 1 and 2 → 2 ways
• n = 3: 1 + 1 + 1, 1 + 2, and 2 + 1 → 3 ways

The input constraint is 1 <= n <= 45.

The interview-ready Climbing Stairs solution is:

1. Define the number of ways to reach each step.
2. Partition those ways by their final move.
3. Derive the recurrence.
4. Keep only the two previous values because each state depends on a fixed two-value window.

That gives O(n) time and O(1) extra space. The Fibonacci connection is real, but it is the consequence—not the starting point—of the derivation.

Recognize the final-move pattern

Suppose we want to count the ways to reach step i.

Every valid sequence reaching i must end in exactly one of two ways:

1. A 1-step move from i - 1
2. A 2-step move from i - 2

These groups are:

• Exhaustive: every valid sequence must use one of those two final moves.
• Disjoint: a sequence ending with a 1-step move cannot also end with a 2-step move.

Therefore, we can add the counts:

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

This is a counting problem, so we add both groups. We are not choosing the cheaper, larger, or smaller option.

Define the state directly:

dp[i] = number of distinct sequences that reach exactly step i

This is the recognition cue to remember:

If every solution reaching position i can be partitioned by a small set of possible final moves, define a state for position i and count each final-move group.

Because each value depends on the previous two values, the sequence resembles Fibonacci numbers. That observation is useful for recognition, but it is not a proof. The final-move decomposition is the proof-producing idea.

Define the base cases correctly

The recurrence applies when i >= 2:

dp[i] = dp[i - 1] + dp[i - 2]

Now define the two starting values.

Step 0

Set:

dp[0] = 1

This represents one way to be at the starting position before making any moves: choose the empty sequence.

It does not mean that a move of length zero exists. It is a counting convention that lets the recurrence account for paths that begin with a 2-step move.

Step 1

There is exactly one way to reach step 1:

dp[1] = 1

The sequence is simply:

1

These are the base cases. The recurrence begins at step 2:

dp[2] = dp[1] + dp[0]
      = 1 + 1
      = 2

Those two sequences are 1 + 1 and 2.

The first values are:

Step i	dp[i]	Reason
0	1	One empty sequence at the start
1	1	1
2	2	1 + 1, 2
3	3	dp[2] + dp[1]
4	5	dp[3] + dp[2]
5	8	dp[4] + dp[3]

A common mistake is to initialize dp[0] = 0 because “zero steps should have zero ways.” That breaks the transition for step 2:

dp[2] = dp[1] + dp[0] = 1 + 0 = 1

The direct path 2 disappears. A base case must support the recurrence, not merely sound intuitive in isolation.

The external problem contract starts at n = 1, so the public function does not need to accept n = 0. Internally, however, dp[0] = 1 is still the cleanest model. If a variant allowed n = 0, this same convention would return 1 for the empty sequence.

Start with recursion, then remove repeated work

The recurrence naturally gives us a recursive function:

ways(i):
    if i == 0: return 1
    if i == 1: return 1
    return ways(i - 1) + ways(i - 2)

This is a correct description of the problem, but it repeats subproblems.

To compute ways(5), we need ways(4) and ways(3). Computing ways(4) also needs ways(3). The same state appears in multiple branches of the recursion tree.

That is the signal for dynamic programming: the problem has overlapping subproblems. Several paths ask for the same answer, so compute that answer once and reuse it.

Memoization

Memoization caches the result for each step:

ways(i):
    if i is already cached:
        return cache[i]

    cache[i] = ways(i - 1) + ways(i - 2)
    return cache[i]

With memoization, each step index is computed once. The repeated recursion still describes the decomposition, but the cache prevents repeated calculation.

Memoized recursion uses:

• Time: O(n)
• Extra space: O(n) for the cache and recursive call stack

Memoization is often a good first implementation when the recursive structure is easier to discover. Here, though, the dependency direction is a straight line: every state depends only on earlier states. That makes bottom-up iteration simpler and avoids recursion overhead.

Compress the table to two variables

The full table is useful for reasoning:

dp[i] = dp[i - 1] + dp[i - 2]

But the transition reads only two earlier entries. Once dp[i] has been computed, values older than dp[i - 2] can never be used again.

So we retain only the dependency window:

• two_back stores dp[i - 2]
• one_back stores dp[i - 1]

def climb_stairs(n: int) -> int:
    # dp[0] = 1: the empty sequence at the starting position
    two_back = 1

    # dp[1] = 1: one 1-step move
    one_back = 1

    if n == 1:
        return one_back

    for step in range(2, n + 1):
        next_ways = two_back + one_back
        two_back = one_back
        one_back = next_ways

    return one_back

The update order is part of the algorithm. Compute next_ways before changing either old value:

next_ways = dp[i - 2] + dp[i - 1]
two_back  = dp[i - 1]
one_back  = dp[i]

If you update two_back first, you may destroy one of the inputs needed to calculate the next state.

For n = 5, the variables move like this:

Target step	two_back	one_back	next_ways
Start	dp[0] = 1	dp[1] = 1	—
2	1	1	2
3	1	2	3
4	2	3	5
5	3	5	8

The function returns 8.

Rolling state is a storage optimization, not a different recurrence. The state definition and correctness argument stay the same; only the amount of remembered history changes.

Prove the recurrence and implementation

A short induction argument establishes correctness.

• Base cases: dp[0] = 1 represents the empty sequence at the starting position. dp[1] = 1 represents the only sequence reaching step 1.
• Inductive step: Assume the counts for steps i - 1 and i - 2 are correct. Every sequence reaching i ends either with a 1-step move from i - 1 or a 2-step move from i - 2. The groups are disjoint and exhaustive, so their counts can be added.
• Therefore, dp[i] is correct. Repeating this argument computes the correct answer through step n.

The rolling implementation preserves the same invariant:

Before each loop iteration for target step i, two_back equals dp[i - 2] and one_back equals dp[i - 1].

The calculation creates dp[i], then shifts the window forward. After the final iteration, one_back equals dp[n], which is the required answer.

Check edge cases and complexity

The small valid inputs expose most indexing mistakes:

• n = 1 returns 1.
• n = 2 computes 1 + 1 = 2.
• n = 3 computes 1 + 2 = 3.

The input contract excludes n = 0, so the function does not need a public n == 0 branch. The internal dp[0] value still matters because it represents the empty starting sequence and supports the transition into step 2.

Complexity

The loop runs once for each step from 2 through n. Each iteration performs constant work.

• Time: O(n)
• Extra space: O(1)

A full bottom-up table would use O(n) space. Memoized recursion also uses O(n) auxiliary space for its cache and call stack.

For the stated constraint 1 <= n <= 45, the iteration count is small. In another language, also check that the chosen numeric type can represent the possible answer range. That is an implementation concern separate from the recurrence.

Failure modes to catch in an interview

• Updating too early: Compute next_ways before shifting either variable.
• Returning the stale variable: After the final update, one_back contains dp[n]; two_back contains dp[n - 1].
• Mixing indexing models: Decide whether your state refers directly to step numbers or to shifted array positions. Do not switch conventions halfway through.
• Using dp[0] = 0: Under this recurrence, that removes the direct 2-step path from dp[2].
• Treating order as irrelevant: 1 + 2 and 2 + 1 reach the same height, but they are different sequences and both count.
• Calling the pattern “Fibonacci” too early: The label does not tell you the state meaning, base cases, or update order. Derive those first.

The reusable pattern

When you see a one-dimensional counting problem, ask:

1. What does one state count?
2. What could the final move have been?
3. Do the final-move groups overlap?
4. Do they cover every valid solution?
5. Which boundary values make the recurrence valid?
6. Does the next state need the whole table or only a fixed-size dependency window?

For Climbing Stairs, the answers are compact: one state per destination step, two possible final moves, addition across disjoint groups, and two retained previous values.

That is the transferable reasoning move. Derive the recurrence first. Then make memory match the dependency window. When the dependency is fixed and narrow, the table is a teaching tool; the rolling state is the implementation.