LeetCode 509. Fibonacci Number

파이썬 알고리즘 인터뷰 85번(리트코드 509번) Fibonacci Number
https://leetcode.com/problems/fibonacci-number/

나의 풀이1(DP - Tabulation)

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        seq = [0, 1]
        for _ in range(n - 1):
            seq.append(seq[-1] + seq[-2])
        return seq[-1]

나의 풀이2

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

• 생각해보니 전부 저장해둘 필요가 없다.

다른 풀이1(DP - Memoization)

class Solution:
    memo = collections.defaultdict(int) # memo를 fib 안에서 정의하면 느리다.
    memo[0] = 0
    memo[1] = 1
    def fib(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]

        return self.fib(n - 1) + self.fib(n - 2)

• memo를 fib안에서 정의하면 fib이 호출될 때마다 memo가 초기화되므로 그 역할을 못하고 느리다.

다른 풀이2(DP - Tabulation)

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