구간 DP, 크누스 최적화
[1. 개요]구간 DP 크누스 최적화크누스 최적화는 구간 DP의 특정 조건을 만족할 때, 시간복잡도를 줄일 수 있는 방법최적 분할점은 단조롭게 증가한다는 성질을 이용한다.[2. 구간 DP]bottom-up[3. 크누스 최적화]아래와 같은 조건을 만족할 때 적용 가능하다.cost(a, c) + cost(b, d) # 사각 부등식# a # 구간이 겹칠 때 비용 합이, 큰 구간과 작은 구간의 비용합보다 크지 않아야 한다.cost(b, c) # a # 작은 구간의 비용이 큰 구간의 비용보다 크지 크지 않아야 한다.이 때, [i, j] 를 나누는 구간 k 를 설정하기 위해, [i, j] 를 탐색 범위로 잡는 것이 아니고,opt[i][j] ( 구간 [i, j] 를 최적으로 분할하는 위치 ) 를 k 라 할 때, k..