Thinking recursively

Climbing n stairs, 1 or 2 at a time: your last move came from stair n − 1 or n − 2. So ways(n) = ways(n − 1) + ways(n − 2).

Written directly, it recomputes the same answers again and again. Remembering them (with @lru_cache from functools) makes it instant. That idea is dynamic programming.

1from functools import lru_cache
2 
3@lru_cache(maxsize=None)
4def ways(n):
5    if n <= 2:
6        return n
7    return ways(n - 1) + ways(n - 2)