[Dynamic Programming] #509. Fibonacci Number

[전체 code]

class Solution(object):
    def fib(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            F = [0 for i in range(n+1)]
            F[0] = 0
            F[1] = 1
            for i in range(2,n+1):
                F[i] = F[i-1] + F[i-2]

유명한 Fibonacci number를 구하는 문제이다. F[N] 을 구하기 위해 이전 피보나치 수인 F[N-1]과 F[N-2]를 이용하는 Dynamic Programming 문제였다.

시간 복잡도: O(N)
for loop을 한 번만 돌면서 F[N]을 이전에 저장된 두 수의 덧셈으로 구하기 때문에 O(N)이다.