리트코드 509번 Fibonacci Number (python)

Problem

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

Solution

내 풀이

class Solution:
    def fib(self, n: int) -> int:
        fb = []

        def dp(n):
            if n == 0:
                return 0
            elif n == 1:
                return 1
            else:
                return fb[n - 1] + fb[n-2]

        for i in range(n+1):
            fb.append(dp(i))

        return fb[-1]

fb[i]는 i번째 피보나치 수를 의미한다. 0부터 n까지 원하는 값까지 하나씩 구하는 방식이다.

다른 풀이

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]

dictionary를 응용한 풀이이다. 위에서 아래로 하향식 풀이방법이다.

Reference

파이썬 알고리즘 인터뷰 85번