정의

• 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 겹치는 문제의 경우 메모이제이션 기법을 사용하여 주어진 문제를 푼다. 한마디로 분할정복1) + 메모이제이션 기법이라고 할 수 있다
• 문제의 최적 해결 방법이 부분문제에 대한 최적 해결 방법으로 구성되는 경우의 문제(최적 구분 구조)를 갖고 있는 문제를 풀이할 수 있다.

조건

1. Overlapping subproblem: 겹치는 부분(작은) 문제

   어떤 문제가 여러개의 부분문제로 쪼개질 수 있을때 사용하는 용어

2. Optimal Substructure: 최적 부분구조

   최적 부분 구조일때 문제의 정답을 작은 문제의 정답에서 부터 구할 수 있음

장점

• 모든 가능한 경우를 확인하기 때문에 근사치가 아닌 정확한 값을 얻을 수 있다.

단점

• 다이나믹 프로그래밍의 단점모든 가능한 경우를 확인하기 때문에 알고리즘에 비해 시간 복잡도가 크다.

푸는순서

1. 상태를 정의
2. 점화식을 찾는다
3. 시간복잡도를 계산

푸는 방법