Algorithm/DP
Kruth's optimization
jhg0406
2020. 3. 2. 17:33
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)값을 저장)
가 성립한다.
참고