[Python] Leetcode 509. Fibonacci Number (Easy)

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

Fibonacci Number - LeetCode

정말 유명한 피보나치 DP문제입니다.

매번 피보나치 수를 새로 계산하지 않고 이전의 결과값을 사용해 계산하면 됩니다.

Memoization의 개념과 필요성을 한방에 이해시키는 좋은 문제라고 생각합니다.

 

class Solution:
    def fib(self, n: int) -> int:
        dp = [0] * (31)
        dp[0] = 0
        dp[1] = 1

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

        return dp[n]

for i in range(0,31):
    print(Solution().fib(i))