Knuth's Optimization은 다이나믹 프로그래밍(DP) 문제를 해결하는 데 사용되는 기법으로, 일반적으로 DP의 시간 복잡도를 줄이는 데 도움을 줍니다. 이 기법은 DP 테이블에서의 최적 부분 구조를 활용하여 특정 조건을 만족하는 경우 탐색 공간을 줄여줍니다.
Knuth's Optimization은 특히 "Merging Intervals" 문제, 즉 "Optimal Binary Search Tree" 문제와 같은 문제에서 자주 사용됩니다. 이 기법은 DP 테이블에서의 최적화를 통해 시간 복잡도를 개선할 수 있는 경우에 유용합니다.
기본 아이디어
Knuth's Optimization은 다음과 같은 조건을 만족하는 DP 문제에 적용될 수 있습니다:
- Monotonicity Property: DP 테이블의 인덱스가 증가함에 따라 최적의 선택이 한쪽으로 이동해야 합니다.
- Quadrangle Inequality: 문제의 비용 함수가 사각형 불등식을 만족해야 합니다.
적용 방법
- DP 테이블 정의
- 초기화
- 재귀 관계 정의
- Knuth's Optimization 적용
최적 선택 k가 단조 증가하는 성질을 이용하여 탐색 범위를 좁힘
