class Solution(object):
  def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    pre, cur = 1, 1
    for i in range(1,n):
      pre,cur = cur,pre+cur
    return cur
#测试
tmp = Solution()
print(tmp.climbStairs(10))

class Solution(object):
  def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n == 1:
      return 1
    if n == 2:
      return 2
    res = [1, 2]
    for i in range(2, n):
      res.append(res[i - 1] + res[i - 2])
    return res[-1]
#测试
tmp = Solution()
print(tmp.climbStairs(10))