fibonacci numbers

# TC: O(n)
# SC : O(N)

class Solution:
    # TC: O(n)
    # SC : O(N)
    def fib(self, n: int) -> int:
        mem = {}
        if n == 1:
            return 1
        if n == 0:
            return 0
        if n in mem:
            return mem[n]

        mem[n] = self.fib(n-1) + self.fib(n-2)
        return mem[n]

    # TC: O(n)
    # SC : O(1)
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        current = 0
        prev1 = 1
        prev2 = 0

        for i in range(2, n+1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return current