Knuth Optimization
크누스 최적화로 구간 DP O(N^3) -> O(N^2). DP 테이블을 구간 길이 순으로 채우며, 각 dp[i][j]의 k 탐색 범위를 opt[i][j-1] <= k <= opt[i+1][j] 로 제한한다.
메타데이터
| ID | knuth |
| 카테고리 | algorithm |
| 버전 | v4 |
| 길이 | 13.0s (13000ms) |
| 구성 | 21 elements · 4 chapters · 4 effects |
| 태그 | #algorithm #dp #optimization #divide-and-conquer |
본문에 삽입
```anim:knuth
{}
```