class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
#dp[n]=dp[n-1]+dp[n-2]
#1-1,2-2,3-3,4-5,5-8
#a b a b a
#O(1)
"""
a=b=1#dp[0]=0,dp[1]=1
for i in range(1,n):
if i%2==1:
a+=b
else:
b+=a
return max(a,b)
"""
dp=[0]*(n+1)
dp[0]=dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
