LC 0509 [E] Fibonacci Number - ALawliet/algorithms GitHub Wiki

class Solution:
    cache = {0: 0, 1: 1}

    def fib(self, N: int) -> int:
        if N in self.cache:
            return self.cache[N]
        self.cache[N] = self.fib(N - 1) + self.fib(N - 2)
        return self.cache[N]

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