```
import math
class Solution(object):
# def __init__(self):
# self.map = {}
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
p = (1+math.sqrt(5))/2.
q = (1-math.sqrt(5))/2.
return int( (p**(n+1) - q**(n+1)) / (p-q) )
```