ほぼ日刊競プロ leetcode　70. Climbing Stairs

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

考えたこと

0段の階段だと１パターン（今回は１段以上だが）,１段の階段の登り方は１パターン，２段の階段の登り方は２パターン，３段の階段の登り方は３，４段の階段の登り方は５となる．

つまり(0),1,1,2,3,5,8,13,21,34,55,89と増えていく
つまりフィボナッチ数列となる．

最初は以下のように再帰的に書いたらタイムアウトしてしまった．

class Solution:
   def climbStairs(self, n: int) -> int:
       if n==1 or n==0:
           return 1
       else:
           return self.climbStairs(n-2)+self.climbStairs(n-1)

なので無難にfor文で書いてみた．

class Solution:
   def climbStairs(self, n: int) -> int:
       #0, 1, 1, 2, 3, 5, 8, 13, 21
       a=0
       b=1
       for i in range(n):
           #a, b = b, a+b
           temp = b
           b = a + temp
           a = temp
       
       return b