_

1. 소개

DP을 사용해 문제를 푸는 과정에서 특정 형태의 점화식을 갖는 문제들에서는 최적화 기법을 통해 시간복잡도를 줄일 수 있는데, 이를 DP Optimization(동적 계획법 최적화)라고 한다. 문제에서 구해낸 점화식에 따라 그에 맞는 최적화 기법을 사용하여 더 빠른 시간에 동작하는 코드를 짤 수 있어야 한다.

2. 종류

• Divide & Conquer Optimization
• Knuth Optimization
• Convex Hull Trick