DP

다이나믹 프로그래밍 (DP)

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
  • Overlapping Subproblem
    • 큰 문제와 작은문제를 같은 방식으로 해결 가능
    • 문제를 작은 문제로 분리 가능
  • Optimal Substructure
    • 문제의 정답을 작은 문제의 정답에서 구할 수 있음
• Optimal Substructure을 만족하므로, 같은 문제는 구할 때마다 정답이 같다.
• 따라서 정답을 한 번 구했으면, 배열에 저장해놓는 식으로 메모해놓는다.

DP의 해결방법

• Top-down

  • 문제를 작은문제로 나눠 작은문제를 먼저 해결한 후, 문제를 푼다.
  • 보통 재귀 호출을 이용해서 해결

• Bottom-up

  • 크기가 작은 문제부터 차례로 푼다.