```
class Solution:
# @param n, an integer
# @return an integer
def __init__(self):
pass
def climbStairs(self, n):
debug = 1
if n < 2:
return n
numones = {}
numtwos = {}
dp = {}
numones[1] = 1
numtwos[1] = 0
dp[1] = 1
for i in range(2, n+1):
numones[i] = numones[i-1] + numtwos[i-1]
numtwos[i] = numones[i-1]
dp[i] = numones[i] + numtwos[i]
return dp[n]
```