3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\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\$ – Maarten Fabré Jan 30 '18 at 9:14
  • 2
    \$\begingroup\$ @MaartenFabré: The problem is from leetcode.com, which always requires an unnecessary Solution class. \$\endgroup\$ – Gareth Rees Jan 30 '18 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\$ – Gareth Rees Jan 30 '18 at 11:20
  • \$\begingroup\$ Sure. i used the leetcode preparation. leetcode.com/problems/climbing-stairs \$\endgroup\$ – NinjaG Jan 31 '18 at 0:09
6
\$\begingroup\$

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

@lru_cache(maxsize=None)
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
    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:

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

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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