Dynamic programming solution to "Climbing Stairs"
The code in the post has to compute the \$i\$th Fibonacci number, \$F_i\$, for every \$i \le n\$, in order to compute \$F_n\$. It's possible to do much better than that, by using the recurrence $$ \eqalign{F_{2n−1} &amp;= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &amp;= (2F_{n−1} + F_{n}) F_{n}} $$ combined with memoization. For example, you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    """Return the nth Fibonacci number."""
    if n &lt;= 1:
        return n
    elif n % 2:
        a = fibonacci(n // 2)
        b = fibonacci(n // 2 + 1)
        return a * a + b * b
    else:
        a = fibonacci(n // 2 - 1)
        b = fibonacci(n // 2)
        return (2 * a + b) * b


this computes the \$10^6\$th Fibonacci number, which has more than 200,000 decimal digits, in a fraction of a second:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:fibonacci(10**6), number=1)
0.06556476117111742
&gt;&gt;&gt; len(str(fibonacci(10**6)))
208988


By contrast, the code in the post cannot compute Solution().climbStairs(10 ** 6) without running out of memory.