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]

1. Is there any improvement of this code?
2. Is there any alternative way rather than dynamic programming?
• Does the recursion formula remind you of some famous sequence? (Spoiler: codereview.stackexchange.com/questions/96197/…) – Martin R Oct 16 '17 at 19:42
• @MartinR, yes. It shows a lot of ways. Thanks a lot for sharing. – arsho Oct 16 '17 at 21:08

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