알고리즘/DP
2021. 11. 8.
Divide and Conquer Optimization
DP를 최적화 하는 방법 중 하나인 Divide and Conquer Optimization에 대해 알아봅시다. DnC Optimization은 DP점화식이 다음과 같은 형태일 때 사용할 수 있습니다. 1. DPi,j=min 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일 때 사용할 수 있습니다. 그래서 어떻게 최적화 ..
