리트코드 - 509. Fibonacci Number

문제

https://leetcode.com/problems/fibonacci-number/

Fibonacci Number - LeetCode

 

코드

1) Memoization (Top-Down, 하향식)

하향식(Top-Down) 경우 하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어나가는 방법이다. 흔히 이를 Memoization이라고 부른다.

d = [0] * 100

def fib(x)
    if x==1 or x==2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fib(x-1) + fib(x-2)
    return d[x]

 

class Solution:
    dp = collections.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]

 

2) Tabulation (Bottom-up, 상향식)

상향식(Bottom-Up)은 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용하여 큰 문제의 정답을 풀어나가는 방법이다.

d = [0] * 100
    
d[1] = 1
d[2] = 1

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

return d[n]

 

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

 

3) 두 변수만 이용해 공간 절약

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