[LeetCode] 509. Fibonacci Number (Python)

• 문제에 정답이 거의 나와 있어서 이지인 듯

Solution

import collections


class Solution:

    dp = collections.defaultdict(int)

    def fib(self, n: int) -> int:
        # 피보나치 정의: n >= 2
        if n <= 1:
            return n

        # dp[n]이 존재할 때는 그냥 리턴
        if self.dp[n]:
            return self.dp[n]

        # dp[n]이 존재하지 않는 값이라면
        # 계산한 값을 dp[n]에 저장해둠
        self.dp[n] = self.fib(n - 1) + self.fib(n - 2)
        # 그리고 바로 리턴
        return self.dp[n]

Reference

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