<aside> 🔥 다이나믹 동적 프로그래밍이란?

• 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 합하여 풀이하는 알고리즘.
• 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해 나간다.
• 중요한것은 중복된 문제란 점이며, 중복되지 않는 문제들은 다이나믹으로 풀지 않는다.

</aside>

<aside> 🔥 다이나믹 프로그래밍 방법론

방식에 따라 크게 상향식(타뷸레이션), 하향식(메모이제이션)으로 나눌 수 있다.

1. 상향식 (Tabulation)

   더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다.

   # 피보나치 수열 상향식 예시
   def fib(n):
   dp[0] = 0
   dp[1] = 1
   
   for i in range(2, n + 1):
   	dp[i] = dp[i - 1] + dp[i - 2]
   return dp[n]
   

2. 하향식 (Memoization)

   하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어 나간다.

   # 피보나치 수열 하향식 예시
   def fib(n):
   	if n <= 1:
   		return m
   	
   	if dp[n]:
   		return dp[n]
   	
   	dp[n] = fib(n - 1) + fib(n - 2)
   	return dp[n]
   

</aside>