You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:


Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:


Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Difficulty: introductory

Starter code:

class Solution:
    def climbStairs(self, n: int) -> int:
        

Solutions:
class Solution:
     
     dictionary = {}
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         number = 0
         if n == 0 or n == 1:
             return 1
         if n in self.dictionary:
             return self.dictionary[n]
         else:
             number += self.climbStairs(n - 1) + self.climbStairs(n - 2)
             self.dictionary[n] = number
         return number

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         result = [1 for i in range(n+1)]
         for i in range(2, n + 1):
             result[i] = result[i - 1] + result[i - 2]
         return result[n]

class Solution:
     def climbStairs(self, n):
         T = [1, 1]
         for i in range(2, n+1):
             T[i%2] = T[(i - 2)%2] + T[(i-1)%2]
         return T[n%2]
     
     
     def iterative_climbStairs(self, n):
         T = [-1]*n
         T[0] = 0
         T[1] = 1
         for i in range(2, n+1):
             T[i] = T[i - 2] + T[i - 1]
         return T[n]
         
     
     def recursive_climbStairs(self, T, n):
         """
         :type n: int
         :rtype: int
         """
         if (n in T):
             return T[n]
         if (n < 0):
             return 0
         if (n < 2):
             return 1
         T[n] = self.climbStairs(n - 2) + self.climbStairs(n - 1)
         return T[n]

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         steps = [0, 1, 2]
         if n < 3:
             return steps[n]
         for i in range(3,n+1):
             steps.append(steps[i-1] + steps[i-2])
         return steps[n]

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         # f(i) = f(i-1) + f(i-2)
         if n == 0 or n == 1:
             return 1
         f2, f1 = 1, 1
         for i in range(2, n+1):
             f = f1 + f2
             f2, f1 = f1, f
         return f
     
     def climbStairs(self, n):
         F = {0:1, 1:1}
         def f(i):
             if i in F:
                 return F[i]
             else:
                 F[i] = f(i-1) + f(i-2)
                 return F[i]
         return f(n)

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n == 1:
             return 1
         
         dp = [0]*(n+1)
         dp[0] = 1
         dp[1] = 1
         
         for i in range(2,n+1):
             dp[i] += dp[i-1] +dp[i-2]
         return dp[n]


class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n < 3:
             return n
         a = [1, 2]
         for i in range(2, n):
             a.append(a[i-1] + a[i-2])
         return a[n-1]

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n<=3:
             return n
 
         v=[1,2,3]
         for i in range(3,n):
             v.append(v[-1]+v[-2])
         return v[-1]

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         a = 1
         b = 2
         if n < 2:
             return 1
         for i in range(n-2):
             a,b = b, a+b
             
         return b

class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         #递归超时。。
         # if n == 1:
         #     return 1
         # if n == 2:
         #     return 2
         # return self.climbStairs(n-1)+self.climbStairs(n-2)
     
         #改进递归，使用cache
         cache = {}
         def f(n):
             if n == 1:
                 return 1
             if n == 2:
                 return 2
             if n in list(cache.keys()):
                 return cache[n]
             cache[n] = f(n-1) + f(n-2)
             return cache[n]
         return f(n)
         
     
         #改成循环。递推公式为。f(n) = f(n-1) + f(n-2)
         


class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         # n[0] = 1
         # n[1] = 1
         # n[2] = n[0] + n[1]
         # n[3] = n[1] + n[2]
         # n[4] = n[2] + n[3]
         
         if n == 0 or n == 1:
             return 1
         
         ns = [1, 1]
         for i in range(2, n):
             ns[i%2] = sum(ns)
             
         return sum(ns)
         


class Solution:
     def climbStairs(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 0:
             return 0
         if n==1:
             return 1
         if n==2:
             return 2
         a, b=1,2
         for i in range(n)[2:]:
             a,b=b,a+b
         return b