알고리즘/DP
2021. 11. 8.
Divide and Conquer Optimization
DP를 최적화 하는 방법 중 하나인 Divide and Conquer Optimization에 대해 알아봅시다. DnC Optimization은 DP점화식이 다음과 같은 형태일 때 사용할 수 있습니다. 1. \(DP_{i, j} = \min_{k < j}(DP_{i-1, k} + C_{k, j})\) 2. \(A_{i, j}\)가 위 식에서 \(DP_{i, j}\)가 최소값이 되기 위한 최소 \(k\)라고 했을 때, \(A_{i, j} \le A_{i, j+1}\) 풀어서 얘기하면, \(DP_{i, j}\)가 최소가 되는 \(k\)를 \(x\)라고 하고, \(DP_{i, j+1}\)가 최소가 되는 \(k\)를 \(y\)라고 했을 때, \(x \le y\)일 때 사용할 수 있습니다. 그래서 어떻게 최적화 ..
