Dynamic Programming

제일 작은, 간단한 방법을

순차적으로, 누적하며 진행하여 큰 값을 구하는 방식

초기 조건 설정과 점화식 세우기가 중요

 

 

피보나치 점화식을 통해 설명하자면,

점화식은 다음과 같다

Fn = Fn-1 + Fn-2

 

보통 이를 재귀함수로 구현했을 때 코드는 다음과 같다

def fibo(n):
	if n < 3:
    	return 1
    return fibo(n-1) + fibo(n-2)

n번째라는 큰 숫자를 넣고 n-1, n-2를 해가며 작아지는 top-down 형식이

바로 재귀 Recursion을 쓴 것

 

 

그럼 Dynamic Programming은 이와 다르게

작은 규칙들을 하나씩 쌓아 올려 큰 값에 도달하는 bottom-up 형식

n = 5   # 몇 번째 피보나치 수를 출력할 것인가

d = [0]*(n+1)
d[1] = d[2] = 1
# 1 1 2 3 5 8 .. 에서 앞에 두 개

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