Knuth Optimization

DP Optimization Technique

정의

$ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다.

 

$ dp[i][j] = \min_{i<k<=j} ( dp[i][k-1] + dp[k][j] ) + cost[i][j] \quad for \quad i < j$

 

$A[i][j]$를 $dp[i][j]$를 최적으로 만드는 $k$라 하자.

$i<j일 때 A[i][j-1] <= A[i][j] <= A[i+1][j]$를 만족한다.

 

 

조건

1. 단조성

$ a<=b<=c<=d \quad ->  \quad cost[b][c] <= cost[a][d] $

 

2. Monge Array - 사각 부등식 만족

$ a<=b<=c<=d \quad ->  \quad cost[a][c] + cost[b][d] <= cost[a][d] + cost[b][c] $

 

Monge Array의 성질은 여기에 잘 나와 있다.

 

적용

$i<j일 때 \quad A[i][j-1] <= A[i][j] <= A[i+1][j]$.

1. $(j-1) - i = j - (i+1) = j - i -1$

2. $j - i -1 < j - i$

 

즉, $j-i$가 증가하는 순서대로 dp 테이블을 채우면 $O(n^2)$에 완료할 수 있다.

$j = i + k$일 때 시간복잡도는 다음과 같다.

$\sum A[i+1][i+k] - A[i][i+k-1] -> (텔레스코핑) ->  A[n-k+1][n] - A[1][k]  = O(n) $

 

$ 1 <= k <= n-1 $이므로 $O(n^2)$에 전체 dp 테이블을 채울 수 있다.

 

 

증명

구사과님의 블로그에 따르면, 이 논문에 증명이 나와 있다.

엄밀하다.

 

연습 문제

파일 합치기2 

문자열 자르기

Painting

 

공부한 문서

동적 계획법을 최적화하는 9가지 방법 (2/4) , 구사과

dp optimizations