[코테] 리트코드 다이나믹 프로그래밍 509. Fibonacci Number

509. Fibonacci Number

문제 링크

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

문제 설명

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

• F(0) = 0, F(1) = 1
• F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

제한 사항

• 0 <= n <= 30

입출력 예 #1

1. Input : n = 2
2. Output : 1
3. Explanation : F(2) = F(1) + F(0) = 1 + 0 = 1.

입출력 예 #2

1. Input : n = 3
2. Output : 2
3. Explanation : F(3) = F(2) + F(1) = 1 + 1 = 2.

입출력 예 #3

1. Input : n = 4
2. Output : 3
3. Explanation : F(4) = F(3) + F(2) = 2 + 1 = 3.

문제 풀이

1. (하향식) 재귀 구조 브루트 포스
2. (하향식) 메모이제이션
3. (상향식) 타뷸레이션
4. (상향식) 두 변수만 이용해 공간 절양

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1 :
            return n
        return self.fib(n-1) + self.fib(n-2)

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]

class Solution:
    dp = collections.defaultdict(int)

    def fib(self, n: int) -> int:
        self.dp[1] = 1

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

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