Kruth's optimization

Kruth's optimization

점화식이 

dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j]

비슷한 형태이고 C[i][j]에 대해서

 

조건 1) 사각부등식

C[a][c] + C[b][d] <= C[a][d] + C[b][c]  (a <= b <= c <= d)

 

조건 2) 단조증가

C[b][c] <= C[a][d]  (a <= b <= c <= d)

 

 

에 대해 만족하면, 

num[i][j-1] <= num[i][j] <= num[i+1][j]

(num[i][j] : dp[i][k] + dp[k][j]가 최소가 되게 하는 k(i < k < j)값을 저장)

가 성립한다.

 

 

 

참고

https://wiki.algo.is/Knuth's%20optimization

https://js1jj2sk3.tistory.com/3