[LeetCode] Fibonacci number (dp, 파이썬)

이런 방식으로 하면 공간복잡도(1) 시간복잡도(n)으로 아주 효율성이 좋다

class Solution:
    def fib(self, N: int) -> int:
        x,y=0,1
        for _ in range(N):
            x,y=y,x+y
        return x
        

기본 메모이제이션 풀이

from collections import defaultdict
class Solution:
    dict=defaultdict(int)
    def fib(self, N: int) -> int:
        if N<=1:
            return N
        
        if self.dict[N]:
            return self.dict[N]
        self.dict[N]=self.fib(N-1)+self.fib(N-2)
        return self.dict[N]