1. 브루트포스

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n-1) + self.fib(n-2)
        

갔던 거 또 가는 비효율적인 풀이

2. 메모이제이션

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

메모이제이션
이미 한 번 돌아갔던 값은 저장해서 가지치기

3. 타뷸레이션

class Solution:
    from collections import defaultdict
    dp = defaultdict(int)
    def fib(self, n: int) -> int:
        self.dp[0] = 0
        self.dp[1] = 1
        for i in range(2, n+1):
            self.dp[i] = self.dp[i-1] + self.dp[i-2]
        return self.dp[n]

타뷸레이션 (상향식 풀이)
밑에서부터 반복문으로 값 저장해놓고 부르기 -> 재귀 X

4. 변수 2개

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

굳이 공간복잡도 O(n) 필요 없이 변수 2개면 피보나치 가능