Dynamic programming solution to "Climbing Stairs"

Question

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]

Answer 1

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.

Answer 2

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