DP

일반적인 재귀 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산을 해결하기 위해 등장. 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

💡 사용조건

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
  
  

💡 구현방식

1. 탑다운 방식

재귀 함수를 이용하여 작성
큰 문제를 해결하기 위해 작은 문제를 호출(메모이제이션)

2. 보텀업 방식

단순히 반복문을 이용하여 작성
결과 저장용 리스트(dp테이블)를 만들고 작은 문제부터 차근차근 답을 도출

🤔 특정문제를 완전탐색 알고리즘을 접근했을 때 시간이 매우 오래걸린다면 DP를 적용할 수 있는 지 확인해본다. 또한 가능하다면 보텀업 방식으로 구현하는 것이 좋다!