Dynamic programming solution to "Climbing Stairs" 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 step + 1 step
  2 steps
  
  
  Example 2:
  
  Input: 3 Output:  3 Explanation:  There are three ways to climb to the
  top.
  
  
  1 step + 1 step + 1 step
  1 step + 2 steps
  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]
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.