LeetCode 509. Fibonacci Number Python3 풀이

Dynamic Programming Day 1.

DP의 memoization 방법을 사용한다.

class Solution:
    def fib(self, n: int) -> int:
        fibo = [0 for _ in range(n+1)]

        if n == 0:
            fibo[0] = 0
        else:
            fibo[0] = 0
            fibo[1] = 1

        for _ in range(2, n+1):
            fibo[_] = fibo[_-1] + fibo[_-2]

        return fibo[n]

n이 0일때는 fibo 배열 0번째에 0을 저장
n이 1일때는 fibo 배열 0번째에 0을 저장, 1번째에 1을 저장한다.
이후 index에 해당하는 값은 fibo[_] = fibo[_-1] + fibo[_-2] 를 진행한다.