동적 계획법이란

• 큰 문제를 작은 방법으로 나누어 푸는 알고리즘
• 분할정복(Divide & Conquer)와 비슷하다.
  • 동적 계획법은 작은문제가 중복되지만 분할정복은 절대 불가능하다.

동적 계획법의 조건

• Overlapping Subproblem : 작은 문제
  • 재귀 알고리즘을 통해 해결되는 문제
• Optimal Substructure : 최적 부분구조

Memoization

• 같은 결과를 계속해서 구하는건 비효율적이기 때문에 정답을 한번 구했으면 그 정답을 배열에 저장해 두는 것.
• **시간복잡도를 O(n)**으로 만든다.