Dynamic Programming

점화식 관계가 뚜렷하다면 dp 재귀적 호출 기억하기,,!

(1) top-down 방식 

  : 내가 원하는 값을 구하기 위해 재귀적으로 호출하며 더 낮은 쪽으로 계속 파헤치기 

   (ex) 피보나치 수열 F[n] = F[n-1] + F[n-2] (단, F[0] = 0, F[1] =1)

         

dp = [-1 for _ in range(30+1)]
def fibo(num):
	if num == 0: return 0 
    if num == 1: return 1
    
    if dp[num] != -1: 
    	return dp[num]
    
    dp[num] = dp[num-1] + dp[num-2]
    return dp[num]

print(fibo(30))

 

(2) bottom-up 방식 

   : 가장 작은 항부터 구하고자 하는 항까지 모든 dp 테이블 완성하기 

def fibo(num):
	dp = [-1 for _ in range(num+1)]
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, num+1):
    	dp[i] = dp[i-1] + dp[i-2]

print(fibo(30))