---

🚀 다이내믹 프로그래밍 (DP)

**다이내믹 프로그래밍(Dynamic Programming, DP)**은 복잡한 큰 문제를 더 작은 하위 문제로 나누고, 이 하위 문제들의 해결 결과를 저장해 재사용함으로써 전체 문제의 해결 효율을 높이는 알고리즘 설계 기법입니다.

---

💡 DP 구현 방법

DP는 주로 두 가지 방식으로 구현됩니다.

⬆️ Bottom-Up (반복문)

• 방식: 가장 작은 하위 문제부터 시작하여 계산을 수행하고, 그 결과를 점진적으로 누적하며 더 큰 문제를 해결해 나갑니다.
• 특징: 주로 **반복문(Iteration)**을 사용하여 구현되며, 모든 하위 문제의 답을 명시적으로 계산하여 테이블에 채워나가는 방식입니다.

⬇️ Top-Down (재귀)

• 방식: 해결하려는 가장 큰 문제에서 시작하여, 이 문제를 해결하는 데 필요한 하위 문제들을 재귀적으로 호출합니다. 이때, 이미 계산된 하위 문제의 결과는 저장해두고(메모이제이션), 필요할 때 재활용합니다.
• 특징: 주로 **재귀(Recursion)**와 메모이제이션(Memoization) 기법을 사용하여 구현됩니다.

---

참고 블로그: https://bada744.tistory.com/61