구간 DP, 크누스 최적화

[1. 개요]

구간 DP

 

 

크누스 최적화

• 크누스 최적화는 구간 DP의 특정 조건을 만족할 때, 시간복잡도를 줄일 수 있는 방법
• 최적 분할점은 단조롭게 증가한다는 성질을 이용한다.

---

[2. 구간 DP]

bottom-up

---

[3. 크누스 최적화]

아래와 같은 조건을 만족할 때 적용 가능하다.

1. cost(a, c) + cost(b, d) <= cost(a, d) + cost(b, c)
   # 사각 부등식
   # a <= b <= c <= d
   # 구간이 겹칠 때 비용 합이, 큰 구간과 작은 구간의 비용합보다 크지 않아야 한다.
2. cost(b, c) <= cost(a, d)
   # a <= b <= c <= d
   # 작은 구간의 비용이 큰 구간의 비용보다 크지 크지 않아야 한다.

이 때, [i, j] 를 나누는 구간 k 를 설정하기 위해, [i, j] 를 탐색 범위로 잡는 것이 아니고,

• opt[i][j] ( 구간 [i, j] 를 최적으로 분할하는 위치 ) 를 k 라 할 때, k 의 탐색 범위를 아래와 같이 할 수 있다.
• opt[i][j - 1] <= k <= opt[i + 1][j]
• 구간이 오른쪽 (j 방향) 으로 늘어나면 최적 분할점도 오른쪽으로 밀릴 수 밖에 없다. (오른쪽에 존재할 수 밖에 없다.)

주의 사항

• 재귀 형태 호출에서는 적용 할 수 없다.
• 그 이유는, dp[i][j] 를 계산할 때, dp[i][j-1], dp[i+1][j] 값이 결정되어 있어야 한다.
• bottom-up 방식 구현에서는 이것이 보장된다.
• opt[i+1][j] 값은 j 와 같거나 클 수 없다.
• 구간 [i, j] 를 나누는 k 의 범위는 [i, j) 이기 때문이다.

---

[4. 관련 예제]

• https://testkernelv2.tistory.com/820
•