509. Fibonacci Number

class Solution:
    def fib(self, N: int) -> int:
        memo = {}
        memo[0] = 0
        memo[1] = 1
        if N > 1:
            for i in range(2,N+1):
                memo[i]= memo[i-1]+memo[i-2]
        return memo[N]

# time O(N) space O(1)
class Solution:
    def fib(self, N: int) -> int:
        memo = [0,1,2]
        if N > 1:
            for i in range(2,N+1):
                memo[2]= memo[1]+memo[0]
                memo[0] = memo[1]
                memo[1] = memo[2] 
        return memo[2] if N > 1 else memo[N]

class Solution:
    @lru_cache(None)
    def fib(self, n: int) -> int:
        """ tc O(N) sc O(N)
        1. exit base 
        2. recursive ways 
        """
        if n == 0:
            return 0
        if n == 1 :
            return 1
        return self.fib(n-1) + self.fib(n-2)