Dynamic Programming

import sys

n = sys.stdin.readline()
n = int(n)

#arr = list(map(int, input().split()))

dp = [0] * n
dp[0] = 1
dp[1] = 1


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

print(dp[n-1])

Bottom Up 방식으로 Dynamic Programming을 사용해서 간단하게 작성해본 피보나치 수열.

핵심 아이디어는 반복문을 사용할때 연산된 결과를 dp[]라는 배열에 값으로 저장하고 필요할때마다 불러서 연산을 한다.

즉 큰 문제를 해결하기 위해서 작은 문제로 쪼개서 해결하는 것이다.

재귀호출에 비해서 시간 복잡도에서 훨씬 유리하다. 이는 시간 복잡도가 O(N) 이고 재귀 호출은 O(N^2) 이다.