Count ways to reach the n’th stair I have solved Leetcode climbing-stairs problem which is stated as:


  There are n stairs, a person standing at the bottom wants to reach the
  top. The person can climb either 1 stair or 2 stairs at a time. Count
  the number of ways, the person can reach the top.


I used dynamic programming to solve this like below:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1:
            return 1
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]



Is there any improvement of this code? 
Is there any alternative way rather than dynamic programming?
Pythonic Ideas

Multiplication with lists

You can create an array of n + 1 zeros using the * operator:

dp = [0] * (n + 1)


Which seems a bit clearer (IMHO) than:

dp = [0 for i in range(n+1)]


General solution with no base case

You could get rid of the base case n == 1 if you do:

def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [0] * max(3, n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]




Computing Fibonacci

Your solution is one of the fastest (and most obvious) ways to compute fibonacci with a running time of \$O(n)\$. However, there's a \$O(\log{}n)\$ solution using an interesting property of fibonacci numbers. Here's a proof and an in depth explanation.

Basically if you know F(n) and F(n-1) you can find F(2n) and F(2n-1) following these two formulas:

\begin{aligned}F_{2n-1}&amp;=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&amp;=(F_{n-1}+F_{n+1})F_{n}\\&amp;=(2F_{n-1}+F_{n})F_{n}.\end{aligned}

Using this, you can double your way to the fibonacci number you need (or recursively half your way down)

def fibonacci(n):
    memo = {
        0: 0,
        1: 1,
        2: 1,
        3: 2
    }
    def recurse(n):
        if not n in memo:
            if n % 2 == 0:
                k = n // 2
                memo[k] = recurse(k)
                memo[k - 1] = recurse(k - 1)
                memo[n] = (2 * memo[k - 1] + memo[k]) * memo[k]
            else:
                k = (n + 1) // 2
                memo[k] = recurse(k)
                memo[k - 1] = recurse(k - 1)
                memo[n] = memo[k]**2 + memo[k -1]**2
        return memo[n]
    return recurse(n)


Note: While the closed form solution is interesting, it's not computationally practical since it requires infinate precision of \$\phi\$.