문제. 직선 위에 $n$개의 점이 좌표 $x_i$에 따라 정렬되어 주어집니다. 모든 점을 덮는 $m$개의 선분을 찾되, 선분 길이의 제곱의 합이 최소가 되도록 해야 합니다.
기본 해법은 DP 상태 $f[i, j]$를 최대 $j$개의 선분을 사용하여 처음 $i$개의 점을 덮는 최소 비용으로 정의하는 것입니다. 이 값은 가능한 모든 마지막 선분을 전부 시도하여 갱신할 수 있습니다:
$$ f[i, j] = \min_{k < i} \{f[k, j-1] + (x_{i-1}-x_k)^2 \} $$최종 답은 $f[n, m]$이 되며, 이러한 DP는 전체적으로 $O(n^2 m)$에 동작합니다.
// x[] — отсортированный массив координат точек, индексация с нуля
// квадрат длины отрезка с i-той до j-той точки
int cost(int i, int j) {
return (x[j] - x[i]) * (x[j] - x[i]);
}
for (int i = 0; i <= m; i++)
f[0][i] = 0; // если нам не нужно ничего покрывать, то всё и так хорошо
// все остальные f предполагаем равными бесконечности
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < i; k++)
f[i][j] = min(f[i][j], f[k][j - 1] + cost(k, i - 1));
(i와 j에 대한 반복문은 서로 순서를 바꿀 수 있다는 점에 주목하십시오.)
이 장에서는 이를 최적화하는 서로 연관된 4가지 방법을 살펴보겠습니다. 이 방법들은 이 문제뿐만 아니라 다른 많은 DP에도 일반화하여 적용할 수 있습니다.