LeetCode 70. Climbing Stairs

climbing_stairs.py

"""
You are climbing a staircase. It takes `n` steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
"""

from functools import lru_cache


@lru_cache
def paths_from_step(n: int, k: int = 2) -> int:
    """
    Args:
        n: number of stairs
        k: maximal number stairs climbed per step
    Returns:
        Number of distinct ways to climb to top of `n` stairs, climbing at most `k`
        stairs per step
    """
    if n == 0:
        return 1
    elif n < 0:
        return 0
    else:
        return sum([paths_from_step(n - m, k) for m in range(1, k + 1)])


def main():
    test_cases = [2, 3, 4, 5, 6, 7]
    for test in test_cases:
        print(paths_from_step(test))
    test_cases_2 = [(300, 1), (3, 3), (4, 4), (10, 3)]  # 1  # 4  # 8  # 274
    for test in test_cases_2:
        print(paths_from_step(test[0], test[1]))


if __name__ == "__main__":
    main()

Good explainer here using similar approach from a different perspective (e.g., memoized DFS on binary tree).

Because in this specific case, $k \in \lbrace 1, 2 \rbrace$, we can analytically solve:

$$ \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor } \binom{n-i}{i} , \forall n \in \mathbb{Z}_{\geq 0} $$

...which gives the Fibonnaci sequence zero-indexed by $n$ starting at $1$, i.e., $1, 1, 2, 3, 5, \dots$ ... which is $O(n)$ time complexity 🙃 .

Update: Generalized this problem to any $n, k \in \mathbb{N}$ and switched to out-of-box memoization.

Note that a generator returned by comprehension in L25 will cause a RecursionError¹!

Footnotes

1. https://nedbatchelder.com/blog/201812/a_thing_i_learned_about_python_recursion.html ↩