70. Climbing Stairs

Reformulated question¶

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 this question is 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".

Solution with idiomatic Python¶

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

        # Keep only the last two values.
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

There is no standard-library function that directly solves this exact problem more simply with the same asymptotic behavior, so the iterative DP above is the best direct answer.

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, 1),
        (2, 2),
        (3, 3),
        (4, 5),
        (5, 8),
        (6, 13),
        (10, 89),
        (45, 1836311903),
    ],
)
def test_climb_stairs(n, expected):
    assert Solution().climbStairs(n) == expected

Comment 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)

## Test

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

Code¶

import pytest


class Solution:
    def climbStairs(self, n: int) -> int:
        # Number of ways to reach stair n:
        # ways(n) = ways(n - 1) + ways(n - 2)
        # because the last move is either 1-step or 2-steps.
        if n <= 2:
            return n

        a, b = 1, 2  # ways(1), ways(2)
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b


@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, 1),
        (2, 2),
        (3, 3),
        (4, 5),
        (5, 8),
        (6, 13),
        (10, 89),
        (45, 1836311903),
    ],
)
def test_climb_stairs(n, expected):
    assert Solution().climbStairs(n) == expected


Solution().climbStairs(1)   # 1
Solution().climbStairs(4)   # 5
Solution().climbStairs(10)  # 89