70. Climbing Stairs

Problem¶

Given n stairs, and each move can be 1 or 2 stairs, return how many different sequences of moves reach exactly the top.

Example:

n = 4 -> 5
ways = [1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2]

Key trick¶

The last move to reach stair n is either:

from n - 1 with a 1-step
from n - 2 with a 2-step

So: \(f(n) = f(n-1) + f(n-2)\)

This is Fibonacci with shifted base cases.

Trap¶

Counting paths by explicitly generating them is exponential and unnecessary.
Wrong base cases break everything.
Using recursion without memoization is too slow.

Why is it interesting?¶

It is a tiny DP problem with a very clean recurrence.
It tests whether you can turn "count all possibilities" into "count by last step".

Python solution¶

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev1, prev2 = 1, 2
        for _ in range(n - 2):
            prev1, prev2 = prev2, prev1 + prev2
        return prev2

Comment on my solution¶

Your solution enumerates reachable positions level by level, which duplicates states many times.
It works for small n, but its time and memory are exponential.
The core observation is that only the number of ways to reach each stair matters, not the full list of paths.
ways_nb is indirect and harder to reason about than a recurrence on stair counts.

## Solution

class Solution:
    def climbStairs(self, n: int) -> int:
        ways_nb = 0
        ways = [0] # start at floor 0

        for _ in range(n + 1):
            ways_new = []
            for w in ways:
                w1 = w + 1
                w2 = w + 2
                # we already are at the last floor
                if w1 > n and w2 > n:
                    ways_nb += 1

                if w1 <= n:
                    ways_new.append(w1)
                if w2 <= n:
                    ways_new.append(w2)
            ways = ways_new

        return ways_nb

# new solution after reading AI comment on my first solution
class Solution:
    def climbStairs(self, n: int) -> int:
        # climbStairs(n) = climbStairs(n-2) + climbStairs(n-1)

        if n == 1:
            return 1
        if n == 2:
            return 2

        return self.climbStairs(n-2) + self.climbStairs(n-1)


import pytest

@pytest.mark.parametrize(
    "stairs_number, climbing_ways_number",
    [(1,1), (2,2), (3,3), (4,5)]
)
def test_climbing_stairs(stairs_number, climbing_ways_number):
    assert Solution().climbStairs(stairs_number) == climbing_ways_number