[Algo] DP (dynamic programming)

DP(dynamic programming) 

• 복잡한 문제를 여러 개의 간단한 작은 문제로 나누어 푼 다음 작은 문제의 답을 모아 최종적으로 문제를 해결하는 방법
• "중복되는 부분 문제"와 "최적 부분 구조"를 만족할 때 사용
  • 중복되는 부분 문제(overlapping subproblem): 동일한 부분 문제(작은, 간단한 문제)를 반복적으로 해결
  • 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능
• Memorization, 이전에 해결한 하위 문제의 답을 저장해서 반복 작업을 줄이는 것이 핵심