This is the "Climbing Stairs" problem from leetcode.com:

You are climbing a stair case. It takes \$n\$ steps to reach to the top.

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

Note: Given \$n\$ will be a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

I thought this question is very similar to Fibonacci question. I use dynamic programming,

dp[n] = dp[n - 1] + dp[n - 2]

class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        dp = [1 for i in range(n+1)]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
  • \$\begingroup\$ I don't know whether the algorithm you use is correct, but you don't need a class, a simple function will do, and instead of a function returning a list, a generator yielding the next value will be a lot more efficient \$\endgroup\$ Jan 30, 2018 at 9:14
  • 2
    \$\begingroup\$ @MaartenFabré: The problem is from leetcode.com, which always requires an unnecessary Solution class. \$\endgroup\$ Jan 30, 2018 at 11:19
  • 1
    \$\begingroup\$ @NinjaG: When you post these kinds of questions, could you link to the original problem as well as quoting it, please? The original problem helps answer questions like "why is there a Solution class?" \$\endgroup\$ Jan 30, 2018 at 11:20
  • \$\begingroup\$ Sure. i used the leetcode preparation. leetcode.com/problems/climbing-stairs \$\endgroup\$
    – NinjaG
    Jan 31, 2018 at 0:09

2 Answers 2


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} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (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

def fibonacci(n):
    """Return the nth Fibonacci number."""
    if n <= 1:
        return n
    elif n % 2:
        a = fibonacci(n // 2)
        b = fibonacci(n // 2 + 1)
        return a * a + b * b
        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:

>>> from timeit import timeit
>>> timeit(lambda:fibonacci(10**6), number=1)
>>> len(str(fibonacci(10**6)))

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


As far as I understood, Dynamic Programming uses memoization, and calculatig stuff when needed.

Your algorithm calculates all n values all of the time, while the testing code instantiates the class once, and the queries it multiple times. Yu can use that with something like this:

def climb_stairs_gen():
    a, b = 1, 2
    while True:
        yield a
        a, b = b, a + b

This is a generator which yields ever-increasing values for longer stairs. You use it in the class like this

from itertools import islice
class Solution:
    def __init__(self):
        self.values = []
        self.generator = climb_stairs_gen()

    def climbStairs(self, n):
        :type n: int
        :rtype: int
        val = self.values
        l = len(val)
        if n > l:
            val.extend(islice(self.generator, n - l))
        return val[n - 1]

It checks whether there is a stairs of lenght n or longer is calculated already. If not, it extends the list with pre-calculated values, then it returns the result for the stairs with length n


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.